<!DOCTYPE html>
<html lang="" xml:lang="">
<head>

  <meta charset="utf-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <title>剑指offer</title>
  <meta name="description" content="剑指offer" />
  <meta name="generator" content="bookdown 0.19 and GitBook 2.6.7" />

  <meta property="og:title" content="剑指offer" />
  <meta property="og:type" content="book" />
  
  
  
  

  <meta name="twitter:card" content="summary" />
  <meta name="twitter:title" content="剑指offer" />
  
  
  

<meta name="author" content="高文欣" />


<meta name="date" content="2020-08-26" />

  <meta name="viewport" content="width=device-width, initial-scale=1" />
  <meta name="apple-mobile-web-app-capable" content="yes" />
  <meta name="apple-mobile-web-app-status-bar-style" content="black" />
  
  


<script src="libs/jquery-2.2.3/jquery.min.js"></script>
<link href="libs/gitbook-2.6.7/css/style.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-table.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-bookdown.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-highlight.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-search.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-fontsettings.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-clipboard.css" rel="stylesheet" />











<style type="text/css">
code.sourceCode > span { display: inline-block; line-height: 1.25; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
  { counter-reset: source-line 0; }
pre.numberSource code > span
  { position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
  { content: counter(source-line);
    position: relative; left: -1em; text-align: right; vertical-align: baseline;
    border: none; display: inline-block;
    -webkit-touch-callout: none; -webkit-user-select: none;
    -khtml-user-select: none; -moz-user-select: none;
    -ms-user-select: none; user-select: none;
    padding: 0 4px; width: 4em;
    color: #aaaaaa;
  }
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa;  padding-left: 4px; }
div.sourceCode
  {   }
@media screen {
code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { color: #7d9029; } /* Attribute */
code span.bn { color: #40a070; } /* BaseN */
code span.bu { } /* BuiltIn */
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code span.ch { color: #4070a0; } /* Char */
code span.cn { color: #880000; } /* Constant */
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
code span.dt { color: #902000; } /* DataType */
code span.dv { color: #40a070; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #40a070; } /* Float */
code span.fu { color: #06287e; } /* Function */
code span.im { } /* Import */
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
code span.op { color: #666666; } /* Operator */
code span.ot { color: #007020; } /* Other */
code span.pp { color: #bc7a00; } /* Preprocessor */
code span.sc { color: #4070a0; } /* SpecialChar */
code span.ss { color: #bb6688; } /* SpecialString */
code span.st { color: #4070a0; } /* String */
code span.va { color: #19177c; } /* Variable */
code span.vs { color: #4070a0; } /* VerbatimString */
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
</style>

</head>

<body>



  <div class="book without-animation with-summary font-size-2 font-family-1" data-basepath=".">

    <div class="book-summary">
      <nav role="navigation">

<ul class="summary">
<li class="chapter" data-level="1" data-path=""><a href="#剑指offer题解"><i class="fa fa-check"></i><b>1</b> 剑指offer题解</a><ul>
<li class="chapter" data-level="1.1" data-path=""><a href="#二维数组中的查找"><i class="fa fa-check"></i><b>1.1</b> 二维数组中的查找</a></li>
<li class="chapter" data-level="1.2" data-path=""><a href="#替换空格"><i class="fa fa-check"></i><b>1.2</b> 替换空格</a></li>
<li class="chapter" data-level="1.3" data-path=""><a href="#从头到尾打印链表"><i class="fa fa-check"></i><b>1.3</b> 从头到尾打印链表</a></li>
<li class="chapter" data-level="1.4" data-path=""><a href="#重建二叉树"><i class="fa fa-check"></i><b>1.4</b> 重建二叉树</a></li>
<li class="chapter" data-level="1.5" data-path=""><a href="#两个栈实现队列"><i class="fa fa-check"></i><b>1.5</b> 两个栈实现队列</a></li>
<li class="chapter" data-level="1.6" data-path=""><a href="#旋转数组中最小的数"><i class="fa fa-check"></i><b>1.6</b> 旋转数组中最小的数</a></li>
<li class="chapter" data-level="1.7" data-path=""><a href="#斐波那契数列"><i class="fa fa-check"></i><b>1.7</b> 斐波那契数列</a></li>
<li class="chapter" data-level="1.8" data-path=""><a href="#青蛙跳台阶问题"><i class="fa fa-check"></i><b>1.8</b> 青蛙跳台阶问题</a></li>
<li class="chapter" data-level="1.9" data-path=""><a href="#变态跳台问题"><i class="fa fa-check"></i><b>1.9</b> 变态跳台问题</a></li>
<li class="chapter" data-level="1.10" data-path=""><a href="#矩形覆盖"><i class="fa fa-check"></i><b>1.10</b> 矩形覆盖</a></li>
<li class="chapter" data-level="1.11" data-path=""><a href="#二进制中的1的个数"><i class="fa fa-check"></i><b>1.11</b> 二进制中的1的个数</a></li>
<li class="chapter" data-level="1.12" data-path=""><a href="#数值得整熟次方"><i class="fa fa-check"></i><b>1.12</b> 数值得整熟次方</a></li>
<li class="chapter" data-level="1.13" data-path=""><a href="#调整数组顺序使其位于整熟前面"><i class="fa fa-check"></i><b>1.13</b> 调整数组顺序使其位于整熟前面</a></li>
<li class="chapter" data-level="1.14" data-path=""><a href="#链表的倒数第k个节点"><i class="fa fa-check"></i><b>1.14</b> 链表的倒数第k个节点</a></li>
<li class="chapter" data-level="1.15" data-path=""><a href="#反转链表"><i class="fa fa-check"></i><b>1.15</b> 反转链表</a></li>
<li class="chapter" data-level="1.16" data-path=""><a href="#合并两个有序链表"><i class="fa fa-check"></i><b>1.16</b> 合并两个有序链表</a></li>
<li class="chapter" data-level="1.17" data-path=""><a href="#树的子结构"><i class="fa fa-check"></i><b>1.17</b> 树的子结构</a></li>
<li class="chapter" data-level="1.18" data-path=""><a href="#二叉树的镜像"><i class="fa fa-check"></i><b>1.18</b> 二叉树的镜像</a></li>
<li class="chapter" data-level="1.19" data-path=""><a href="#顺时针打印矩阵"><i class="fa fa-check"></i><b>1.19</b> 顺时针打印矩阵</a></li>
<li class="chapter" data-level="1.20" data-path=""><a href="#包含min函数的栈"><i class="fa fa-check"></i><b>1.20</b> 包含min函数的栈</a></li>
<li class="chapter" data-level="1.21" data-path=""><a href="#栈的压入和弹出顺序"><i class="fa fa-check"></i><b>1.21</b> 栈的压入和弹出顺序</a></li>
<li class="chapter" data-level="1.22" data-path=""><a href="#最小的k个数"><i class="fa fa-check"></i><b>1.22</b> 最小的K个数</a></li>
<li class="chapter" data-level="1.23" data-path=""><a href="#最大子序和"><i class="fa fa-check"></i><b>1.23</b> 最大子序和</a></li>
<li class="chapter" data-level="1.24" data-path=""><a href="#数组中出现次数超过一半的数字"><i class="fa fa-check"></i><b>1.24</b> 数组中出现次数超过一半的数字</a></li>
<li class="chapter" data-level="1.25" data-path=""><a href="#字符串的排序"><i class="fa fa-check"></i><b>1.25</b> 字符串的排序</a></li>
<li class="chapter" data-level="1.26" data-path=""><a href="#有效的括号"><i class="fa fa-check"></i><b>1.26</b> 有效的括号</a></li>
<li class="chapter" data-level="1.27" data-path=""><a href="#找零"><i class="fa fa-check"></i><b>1.27</b> 找零</a></li>
<li class="chapter" data-level="1.28" data-path=""><a href="#点游戏"><i class="fa fa-check"></i><b>1.28</b> 24点游戏</a></li>
<li class="chapter" data-level="1.29" data-path=""><a href="#从上到下打印二叉树"><i class="fa fa-check"></i><b>1.29</b> 从上到下打印二叉树</a></li>
<li class="chapter" data-level="1.30" data-path=""><a href="#二叉树的后续遍历"><i class="fa fa-check"></i><b>1.30</b> 二叉树的后续遍历</a></li>
<li class="chapter" data-level="1.31" data-path=""><a href="#二叉树中和为某一路径值"><i class="fa fa-check"></i><b>1.31</b> 二叉树中和为某一路径值</a></li>
<li class="chapter" data-level="1.32" data-path=""><a href="#复杂链表的复制"><i class="fa fa-check"></i><b>1.32</b> 复杂链表的复制</a></li>
<li class="chapter" data-level="1.33" data-path=""><a href="#反转单词顺序"><i class="fa fa-check"></i><b>1.33</b> 反转单词顺序</a></li>
<li class="chapter" data-level="1.34" data-path=""><a href="#左旋字符串"><i class="fa fa-check"></i><b>1.34</b> 左旋字符串</a></li>
<li class="chapter" data-level="1.35" data-path=""><a href="#把数组排成最小整数"><i class="fa fa-check"></i><b>1.35</b> 把数组排成最小整数</a></li>
<li class="chapter" data-level="1.36" data-path=""><a href="#丑数"><i class="fa fa-check"></i><b>1.36</b> 丑数</a></li>
<li class="chapter" data-level="1.37" data-path=""><a href="#第一个只出现一次的字符串"><i class="fa fa-check"></i><b>1.37</b> 第一个只出现一次的字符串</a></li>
<li class="chapter" data-level="1.38" data-path=""><a href="#数组中的逆序对"><i class="fa fa-check"></i><b>1.38</b> 数组中的逆序对</a></li>
<li class="chapter" data-level="1.39" data-path=""><a href="#两个链表的第一个公共节点"><i class="fa fa-check"></i><b>1.39</b> 两个链表的第一个公共节点</a></li>
<li class="chapter" data-level="1.40" data-path=""><a href="#数字在升序数组中出现的次数"><i class="fa fa-check"></i><b>1.40</b> 数字在升序数组中出现的次数</a></li>
<li class="chapter" data-level="1.41" data-path=""><a href="#平衡二叉树"><i class="fa fa-check"></i><b>1.41</b> 平衡二叉树</a></li>
<li class="chapter" data-level="1.42" data-path=""><a href="#数组中只出现一次的数"><i class="fa fa-check"></i><b>1.42</b> 数组中只出现一次的数</a></li>
<li class="chapter" data-level="1.43" data-path=""><a href="#和为s的连续子序列"><i class="fa fa-check"></i><b>1.43</b> 和为S的连续子序列</a></li>
<li class="chapter" data-level="1.44" data-path=""><a href="#两个数之和为s"><i class="fa fa-check"></i><b>1.44</b> 两个数之和为s</a></li>
<li class="chapter" data-level="1.45" data-path=""><a href="#减绳子"><i class="fa fa-check"></i><b>1.45</b> 减绳子</a></li>
<li class="chapter" data-level="1.46" data-path=""><a href="#机器人的移动范围"><i class="fa fa-check"></i><b>1.46</b> 机器人的移动范围</a></li>
<li class="chapter" data-level="1.47" data-path=""><a href="#矩阵中的路径"><i class="fa fa-check"></i><b>1.47</b> 矩阵中的路径</a></li>
<li class="chapter" data-level="1.48" data-path=""><a href="#滑动窗口的最大值"><i class="fa fa-check"></i><b>1.48</b> 滑动窗口的最大值</a></li>
<li class="chapter" data-level="1.49" data-path=""><a href="#孩子们的游戏"><i class="fa fa-check"></i><b>1.49</b> 孩子们的游戏</a></li>
<li class="chapter" data-level="1.50" data-path=""><a href="#扑克牌的顺子"><i class="fa fa-check"></i><b>1.50</b> 扑克牌的顺子</a></li>
<li class="chapter" data-level="1.51" data-path=""><a href="#将字符串转化为整数"><i class="fa fa-check"></i><b>1.51</b> 将字符串转化为整数</a></li>
<li class="chapter" data-level="1.52" data-path=""><a href="#数组中第一个重复数字"><i class="fa fa-check"></i><b>1.52</b> 数组中第一个重复数字</a></li>
<li class="chapter" data-level="1.53" data-path=""><a href="#构建乘积数组"><i class="fa fa-check"></i><b>1.53</b> 构建乘积数组</a></li>
<li class="chapter" data-level="1.54" data-path=""><a href="#字符串中第一个不重复得字符串"><i class="fa fa-check"></i><b>1.54</b> 字符串中第一个不重复得字符串</a></li>
<li class="chapter" data-level="1.55" data-path=""><a href="#数流中得中位数"><i class="fa fa-check"></i><b>1.55</b> 数流中得中位数</a></li>
<li class="chapter" data-level="1.56" data-path=""><a href="#求n个骰子各点数和出现的概率"><i class="fa fa-check"></i><b>1.56</b> 求n个骰子各点数和出现的概率</a></li>
</ul></li>
</ul>

      </nav>
    </div>

    <div class="book-body">
      <div class="body-inner">
        <div class="book-header" role="navigation">
          <h1>
            <i class="fa fa-circle-o-notch fa-spin"></i><a href="./">剑指offer</a>
          </h1>
        </div>

        <div class="page-wrapper" tabindex="-1" role="main">
          <div class="page-inner">

            <section class="normal" id="section-">
<div id="header">
<h1 class="title">剑指offer</h1>
<p class="author"><em>高文欣</em></p>
<p class="date"><em>2020-08-26</em></p>
</div>
<div id="剑指offer题解" class="section level1">
<h1><span class="header-section-number">1</span> 剑指offer题解</h1>
<p>安装牛客网的顺序的来的~</p>
<div id="二维数组中的查找" class="section level2">
<h2><span class="header-section-number">1.1</span> 二维数组中的查找</h2>
<p><strong>题目描述</strong>
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。</p>
<p>思路：最先想到的遍历一遍数组，判断target是否在数组中即可</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb1-1"><a href="#cb1-1"></a></span>
<span id="cb1-2"><a href="#cb1-2"></a>class Solution<span class="op">:</span></span>
<span id="cb1-3"><a href="#cb1-3"></a><span class="st">    </span><span class="co"># array 二维列表</span></span>
<span id="cb1-4"><a href="#cb1-4"></a><span class="st">    </span>def <span class="kw">Find</span>(self, target, array)<span class="op">:</span></span>
<span id="cb1-5"><a href="#cb1-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb1-6"><a href="#cb1-6"></a><span class="st">        </span><span class="cf">for</span> arr <span class="cf">in</span> array<span class="op">:</span></span>
<span id="cb1-7"><a href="#cb1-7"></a><span class="st">            </span><span class="cf">if</span> target <span class="cf">in</span> arr<span class="op">:</span></span>
<span id="cb1-8"><a href="#cb1-8"></a><span class="st">                </span>return True</span>
<span id="cb1-9"><a href="#cb1-9"></a>        return False</span></code></pre></div>
</div>
<div id="替换空格" class="section level2">
<h2><span class="header-section-number">1.2</span> 替换空格</h2>
<p><strong>题目描述</strong>
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。</p>
<p>思路:</p>
<p>最先能想到replace，哈哈~直接替换</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb2-1"><a href="#cb2-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb2-2"><a href="#cb2-2"></a>import re</span>
<span id="cb2-3"><a href="#cb2-3"></a>class Solution<span class="op">:</span></span>
<span id="cb2-4"><a href="#cb2-4"></a><span class="st">    </span><span class="co"># s 源字符串</span></span>
<span id="cb2-5"><a href="#cb2-5"></a><span class="st">    </span>def <span class="kw">replaceSpace</span>(self, s)<span class="op">:</span></span>
<span id="cb2-6"><a href="#cb2-6"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb2-7"><a href="#cb2-7"></a><span class="st">        </span>return <span class="kw">s.replace</span>(<span class="st">&#39; &#39;</span>,<span class="st">&#39;%20&#39;</span>)</span></code></pre></div>
</div>
<div id="从头到尾打印链表" class="section level2">
<h2><span class="header-section-number">1.3</span> 从头到尾打印链表</h2>
<p><strong>题目描述</strong></p>
<p>输入一个链表，按链表从尾到头的顺序返回一个ArrayList。</p>
<p>从尾到头的顺序，第一个感觉是reverse，但是感觉这么写会被打~</p>
<p>还是一样的问题：有几天</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb3-1"><a href="#cb3-1"></a></span>
<span id="cb3-2"><a href="#cb3-2"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb3-3"><a href="#cb3-3"></a><span class="co"># class ListNode:</span></span>
<span id="cb3-4"><a href="#cb3-4"></a><span class="co">#     def __init__(self, x):</span></span>
<span id="cb3-5"><a href="#cb3-5"></a><span class="co">#         self.val = x</span></span>
<span id="cb3-6"><a href="#cb3-6"></a><span class="co">#         self.next = None</span></span>
<span id="cb3-7"><a href="#cb3-7"></a></span>
<span id="cb3-8"><a href="#cb3-8"></a>class Solution<span class="op">:</span></span>
<span id="cb3-9"><a href="#cb3-9"></a><span class="st">    </span><span class="co"># 返回从尾部到头部的列表值序列，例如[1,2,3]</span></span>
<span id="cb3-10"><a href="#cb3-10"></a><span class="st">    </span>def <span class="kw">printListFromTailToHead</span>(self, listNode)<span class="op">:</span></span>
<span id="cb3-11"><a href="#cb3-11"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb3-12"><a href="#cb3-12"></a><span class="st">        </span>res =<span class="st"> </span>[]</span>
<span id="cb3-13"><a href="#cb3-13"></a>        <span class="cf">while</span> listNode<span class="op">:</span></span>
<span id="cb3-14"><a href="#cb3-14"></a><span class="st">            </span></span>
<span id="cb3-15"><a href="#cb3-15"></a><span class="st">            </span><span class="kw">res.append</span>(listNode.val)</span>
<span id="cb3-16"><a href="#cb3-16"></a>            listNode =<span class="st"> </span>listNode.next</span>
<span id="cb3-17"><a href="#cb3-17"></a>        return res[<span class="op">::-</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="重建二叉树" class="section level2">
<h2><span class="header-section-number">1.4</span> 重建二叉树</h2>
<p><strong>题目描述</strong></p>
<p>输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。</p>
<p><strong>思路</strong>:递归加迭代</p>
<p>知识点：</p>
<p>前序遍历列表：第一个元素永远是 【根节点 (root)】
中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】</p>
<p>算法思路：</p>
<p>通过【前序遍历列表】确定【根节点 (root)】
将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】</p>
<p>就是在考察前序中序后序树的遍历顺序:前序第一个是根节点，找到根节点在中序中的位置，可以划分左右子树，然后递归即可</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb4-1"><a href="#cb4-1"></a>class Solution<span class="op">:</span></span>
<span id="cb4-2"><a href="#cb4-2"></a><span class="st">    </span>def <span class="kw">buildTree</span>(self, preorder<span class="op">:</span><span class="st"> </span>List[int], inorder<span class="op">:</span><span class="st"> </span>List[int]) -&gt;<span class="st"> </span>TreeNode<span class="op">:</span></span>
<span id="cb4-3"><a href="#cb4-3"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(inorder) <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb4-4"><a href="#cb4-4"></a><span class="st">            </span>return None</span>
<span id="cb4-5"><a href="#cb4-5"></a>        </span>
<span id="cb4-6"><a href="#cb4-6"></a>        <span class="co"># 根节点</span></span>
<span id="cb4-7"><a href="#cb4-7"></a>        root =<span class="st"> </span><span class="kw">TreeNode</span>(preorder[<span class="dv">0</span>]) <span class="co">#前序遍历找根节点~</span></span>
<span id="cb4-8"><a href="#cb4-8"></a>        <span class="co"># 获取根节点在 inorder 中的索引</span></span>
<span id="cb4-9"><a href="#cb4-9"></a>        idx =<span class="st"> </span><span class="kw">inorder.index</span>(preorder[<span class="dv">0</span>]) <span class="co"># 找到根节点的索引</span></span>
<span id="cb4-10"><a href="#cb4-10"></a>        <span class="co"># 左子树</span></span>
<span id="cb4-11"><a href="#cb4-11"></a>        root.left =<span class="st"> </span><span class="kw">self.buildTree</span>(preorder[<span class="dv">1</span><span class="op">:</span>idx<span class="op">+</span><span class="dv">1</span>], inorder[<span class="op">:</span>idx]) <span class="co"># </span></span>
<span id="cb4-12"><a href="#cb4-12"></a>        <span class="co"># 右子树</span></span>
<span id="cb4-13"><a href="#cb4-13"></a>        root.right =<span class="st"> </span><span class="kw">self.buildTree</span>(preorder[idx<span class="op">+</span><span class="dv">1</span><span class="op">:</span>], inorder[idx<span class="op">+</span><span class="dv">1</span><span class="op">:</span>])</span>
<span id="cb4-14"><a href="#cb4-14"></a>        return root</span></code></pre></div>
</div>
<div id="两个栈实现队列" class="section level2">
<h2><span class="header-section-number">1.5</span> 两个栈实现队列</h2>
<p>栈：先进后厨
队列：先进先出</p>
<p><strong>题目描述</strong></p>
<p>用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。</p>
<p>找个主要如果用牛客的话需要自己先定义两个空队列</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb5-1"><a href="#cb5-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb5-2"><a href="#cb5-2"></a>class Solution<span class="op">:</span></span>
<span id="cb5-3"><a href="#cb5-3"></a><span class="st">    </span>def <span class="kw">__init__</span>(self)<span class="op">:</span></span>
<span id="cb5-4"><a href="#cb5-4"></a><span class="st">        </span>self.stack1 =<span class="st"> </span>[]</span>
<span id="cb5-5"><a href="#cb5-5"></a>        self.stack2 =<span class="st"> </span>[]</span>
<span id="cb5-6"><a href="#cb5-6"></a></span>
<span id="cb5-7"><a href="#cb5-7"></a>    def <span class="kw">push</span>(self, node)<span class="op">:</span></span>
<span id="cb5-8"><a href="#cb5-8"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb5-9"><a href="#cb5-9"></a><span class="st">        </span><span class="kw">self.stack1.append</span>(node)</span>
<span id="cb5-10"><a href="#cb5-10"></a>    def <span class="kw">pop</span>(self)<span class="op">:</span></span>
<span id="cb5-11"><a href="#cb5-11"></a><span class="st">        </span><span class="co"># return xx</span></span>
<span id="cb5-12"><a href="#cb5-12"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(self.stack2) <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span><span class="st"> </span><span class="co"># 第二个是空队列哦</span></span>
<span id="cb5-13"><a href="#cb5-13"></a><span class="st">            </span><span class="cf">while</span> <span class="kw">len</span>(self.stack1) <span class="op">!=</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb5-14"><a href="#cb5-14"></a><span class="st">                </span><span class="kw">self.stack2.append</span>(self.stack1[<span class="kw">len</span>(self.stack1)<span class="op">-</span><span class="dv">1</span>]) <span class="co"># 先进先出</span></span>
<span id="cb5-15"><a href="#cb5-15"></a>                <span class="kw">self.stack1.pop</span>()</span>
<span id="cb5-16"><a href="#cb5-16"></a>        pop =<span class="st"> </span>self.stack2[<span class="kw">len</span>(self.stack1)<span class="op">-</span><span class="dv">1</span>]</span>
<span id="cb5-17"><a href="#cb5-17"></a>        <span class="kw">self.stack2.pop</span>()</span>
<span id="cb5-18"><a href="#cb5-18"></a>        return pop</span></code></pre></div>
</div>
<div id="旋转数组中最小的数" class="section level2">
<h2><span class="header-section-number">1.6</span> 旋转数组中最小的数</h2>
<p><strong>题目描述</strong></p>
<p>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。</p>
<p>思路：第一感觉，一个min函数不就完事了，但是这么写没有意义，面试官会说你把min的底层写出来~</p>
<p>呵呵 了</p>
<p>因此肯定考排序这里的，比如二分法查找~</p>
<p>保证rotateArray[left]为全场最小，当rotateArray[left]&lt;rotateArray[right]时，证明进入了有序数组，直接输出</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb6-1"><a href="#cb6-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb6-2"><a href="#cb6-2"></a>class Solution<span class="op">:</span></span>
<span id="cb6-3"><a href="#cb6-3"></a><span class="st">    </span>def <span class="kw">minNumberInRotateArray</span>(self, rotateArray,)<span class="op">:</span></span>
<span id="cb6-4"><a href="#cb6-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb6-5"><a href="#cb6-5"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(rotateArray) <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb6-6"><a href="#cb6-6"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb6-7"><a href="#cb6-7"></a>        <span class="co"># 二分法查找,快排</span></span>
<span id="cb6-8"><a href="#cb6-8"></a>        left =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb6-9"><a href="#cb6-9"></a>        right =<span class="st"> </span><span class="kw">len</span>(rotateArray)<span class="op">-</span><span class="dv">1</span></span>
<span id="cb6-10"><a href="#cb6-10"></a>        <span class="cf">while</span> left<span class="op">&lt;</span>right<span class="op">:</span><span class="st"> </span><span class="co">#从左向右开始遍历</span></span>
<span id="cb6-11"><a href="#cb6-11"></a><span class="st">            </span><span class="cf">if</span> rotateArray[left]<span class="op">&lt;</span>rotateArray[right]<span class="op">:</span></span>
<span id="cb6-12"><a href="#cb6-12"></a><span class="st">                </span>return rotateArray[left]</span>
<span id="cb6-13"><a href="#cb6-13"></a>            mid =<span class="st"> </span>left <span class="op">+</span><span class="st"> </span>(right <span class="op">-</span>left)<span class="op">/</span><span class="er">/</span><span class="dv">2</span></span>
<span id="cb6-14"><a href="#cb6-14"></a>            <span class="co"># 左边 有序取另一半</span></span>
<span id="cb6-15"><a href="#cb6-15"></a>            </span>
<span id="cb6-16"><a href="#cb6-16"></a>            <span class="cf">if</span> rotateArray[left]<span class="op">&lt;</span>rotateArray[mid]<span class="op">:</span></span>
<span id="cb6-17"><a href="#cb6-17"></a><span class="st">                </span>left =<span class="st"> </span>mid <span class="op">+</span><span class="dv">1</span></span>
<span id="cb6-18"><a href="#cb6-18"></a>            <span class="co"># 右边有序右边取最小</span></span>
<span id="cb6-19"><a href="#cb6-19"></a>            elif rotateArray[mid]<span class="op">&lt;</span>rotateArray[right]<span class="op">:</span></span>
<span id="cb6-20"><a href="#cb6-20"></a><span class="st">                </span>right =<span class="st"> </span>mid</span>
<span id="cb6-21"><a href="#cb6-21"></a>             <span class="co">#前面两个相等的时候，left进一继续</span></span>
<span id="cb6-22"><a href="#cb6-22"></a>            <span class="cf">else</span> <span class="op">:</span></span>
<span id="cb6-23"><a href="#cb6-23"></a><span class="st">                </span>left<span class="op">+</span><span class="er">=</span><span class="dv">1</span></span>
<span id="cb6-24"><a href="#cb6-24"></a>        return rotateArray[left]</span></code></pre></div>
</div>
<div id="斐波那契数列" class="section level2">
<h2><span class="header-section-number">1.7</span> 斐波那契数列</h2>
<p><strong>题目描述</strong>
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n&lt;=39</p>
<p>直接给出动态规划的解法，省内存</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb7-1"><a href="#cb7-1"></a></span>
<span id="cb7-2"><a href="#cb7-2"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb7-3"><a href="#cb7-3"></a>class Solution<span class="op">:</span></span>
<span id="cb7-4"><a href="#cb7-4"></a><span class="st">    </span>def <span class="kw">Fibonacci</span>(self, n)<span class="op">:</span></span>
<span id="cb7-5"><a href="#cb7-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb7-6"><a href="#cb7-6"></a><span class="st">        </span>num =<span class="st"> </span>{}</span>
<span id="cb7-7"><a href="#cb7-7"></a>        num[<span class="dv">0</span>] =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb7-8"><a href="#cb7-8"></a>        num[<span class="dv">1</span>] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb7-9"><a href="#cb7-9"></a>        <span class="cf">if</span> n <span class="op">&gt;</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb7-10"><a href="#cb7-10"></a><span class="st">            </span><span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">2</span>,n<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb7-11"><a href="#cb7-11"></a><span class="st">                </span>num[i] =<span class="st"> </span>num[i<span class="dv">-2</span>] <span class="op">+</span><span class="st"> </span>num[i<span class="dv">-1</span>]</span>
<span id="cb7-12"><a href="#cb7-12"></a>        return <span class="kw">int</span>(num[n]%(<span class="dv">1000000007</span>))</span>
<span id="cb7-13"><a href="#cb7-13"></a></span>
<span id="cb7-14"><a href="#cb7-14"></a><span class="co"># 绝了，一开始最后的结果没除1000000007取余，死活通不过</span></span></code></pre></div>
</div>
<div id="青蛙跳台阶问题" class="section level2">
<h2><span class="header-section-number">1.8</span> 青蛙跳台阶问题</h2>
<p><strong>题目描述</strong>
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb8-1"><a href="#cb8-1"></a>class Solution<span class="op">:</span></span>
<span id="cb8-2"><a href="#cb8-2"></a><span class="st">    </span>def <span class="kw">jumpFloor</span>(self, number)<span class="op">:</span></span>
<span id="cb8-3"><a href="#cb8-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb8-4"><a href="#cb8-4"></a><span class="st">        </span><span class="cf">if</span> number<span class="op">==</span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb8-5"><a href="#cb8-5"></a><span class="st">            </span>return <span class="dv">1</span></span>
<span id="cb8-6"><a href="#cb8-6"></a>        res=[<span class="dv">1</span>,<span class="dv">2</span>]</span>
<span id="cb8-7"><a href="#cb8-7"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">2</span>,number)<span class="op">:</span></span>
<span id="cb8-8"><a href="#cb8-8"></a><span class="st">            </span><span class="kw">res.append</span>(res[i<span class="dv">-1</span>]<span class="op">+</span>res[i<span class="dv">-2</span>])</span>
<span id="cb8-9"><a href="#cb8-9"></a>        return res[<span class="op">-</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="变态跳台问题" class="section level2">
<h2><span class="header-section-number">1.9</span> 变态跳台问题</h2>
<p>加强版</p>
<p><strong>题目描述</strong></p>
<p>一只青蛙一次可以跳上1级台阶，也可以跳上2级……<em>它也可以跳上n级</em>。求该青蛙跳上一个n级的台阶总共有多少种跳法。</p>
<p>一般<strong>递归</strong>能解决大部分的问题</p>
<p>易知 f(n)=f(n-1)+f(n-2)+……f(1)
f(n-1)=f(n-2)+……f(1)
两式相减得f(n)=2f(n-1)</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb9-1"><a href="#cb9-1"></a>class Solution<span class="op">:</span></span>
<span id="cb9-2"><a href="#cb9-2"></a><span class="st">    </span>def <span class="kw">jumpFloorII</span>(self, number)<span class="op">:</span></span>
<span id="cb9-3"><a href="#cb9-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb9-4"><a href="#cb9-4"></a><span class="st">        </span>n=<span class="dv">1</span> </span>
<span id="cb9-5"><a href="#cb9-5"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">2</span>,number<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb9-6"><a href="#cb9-6"></a><span class="st">            </span>n=<span class="dv">2</span><span class="op">*</span>n</span>
<span id="cb9-7"><a href="#cb9-7"></a>        return n</span>
<span id="cb9-8"><a href="#cb9-8"></a>        </span></code></pre></div>
</div>
<div id="矩形覆盖" class="section level2">
<h2><span class="header-section-number">1.10</span> 矩形覆盖</h2>
<p><strong>题目描述</strong>
我们可以用2<em>1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2</em>1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？</p>
<p><img src="figs/jxfg.png" /></p>
<p>思想：和跳台阶类似，小矩形竖着放相当于跳一级台阶，横着放相当于跳两级台阶，所以可以复用跳台阶的代码（见第八题）。</p>
<div class="sourceCode" id="cb10"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb10-1"><a href="#cb10-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb10-2"><a href="#cb10-2"></a>class Solution<span class="op">:</span></span>
<span id="cb10-3"><a href="#cb10-3"></a><span class="st">    </span>def <span class="kw">jumpFloor</span>(self, number)<span class="op">:</span></span>
<span id="cb10-4"><a href="#cb10-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb10-5"><a href="#cb10-5"></a><span class="st">        </span><span class="cf">if</span> number <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb10-6"><a href="#cb10-6"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb10-7"><a href="#cb10-7"></a>        res =<span class="st"> </span>[<span class="dv">0</span>,<span class="dv">1</span>,<span class="dv">2</span>]</span>
<span id="cb10-8"><a href="#cb10-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">3</span>,number<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb10-9"><a href="#cb10-9"></a><span class="st">            </span><span class="kw">res.append</span>(res[i<span class="dv">-1</span>]<span class="op">+</span>res[i<span class="dv">-2</span>])</span>
<span id="cb10-10"><a href="#cb10-10"></a>        return res[number]</span>
<span id="cb10-11"><a href="#cb10-11"></a>        </span></code></pre></div>
</div>
<div id="二进制中的1的个数" class="section level2">
<h2><span class="header-section-number">1.11</span> 二进制中的1的个数</h2>
<p><strong>题目描述</strong>
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。</p>
<p>其实我jio的一行就行了，bin+count,但是牛客不给通过</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb11-1"><a href="#cb11-1"></a></span>
<span id="cb11-2"><a href="#cb11-2"></a><span class="co">#class Solution:</span></span>
<span id="cb11-3"><a href="#cb11-3"></a>    </span>
<span id="cb11-4"><a href="#cb11-4"></a>   def <span class="kw">NumberOf1</span>(self, n)<span class="op">:</span></span>
<span id="cb11-5"><a href="#cb11-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb11-6"><a href="#cb11-6"></a><span class="st">        </span></span>
<span id="cb11-7"><a href="#cb11-7"></a><span class="st">       </span>return <span class="kw">bin</span>(n)<span class="kw">.count</span>(<span class="st">&#39;1&#39;</span>)</span></code></pre></div>
<p>还是得用正常的方式</p>
<div class="sourceCode" id="cb12"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb12-1"><a href="#cb12-1"></a>class Solution<span class="op">:</span></span>
<span id="cb12-2"><a href="#cb12-2"></a><span class="st">    </span>def <span class="kw">NumberOf1</span>(self, n)<span class="op">:</span></span>
<span id="cb12-3"><a href="#cb12-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb12-4"><a href="#cb12-4"></a><span class="st">        </span>count =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb12-5"><a href="#cb12-5"></a>        <span class="cf">if</span> n <span class="op">&lt;</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb12-6"><a href="#cb12-6"></a><span class="st">            </span>n =<span class="st"> </span>n <span class="op">&amp;</span><span class="st"> </span><span class="dv">0xffffffff</span></span>
<span id="cb12-7"><a href="#cb12-7"></a>        <span class="cf">while</span> n<span class="op">:</span></span>
<span id="cb12-8"><a href="#cb12-8"></a><span class="st">                </span>count <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb12-9"><a href="#cb12-9"></a>                n =<span class="st"> </span>(n <span class="op">-</span><span class="st"> </span><span class="dv">1</span>) <span class="op">&amp;</span><span class="st"> </span>n</span>
<span id="cb12-10"><a href="#cb12-10"></a>        return count</span>
<span id="cb12-11"><a href="#cb12-11"></a>        </span></code></pre></div>
</div>
<div id="数值得整熟次方" class="section level2">
<h2><span class="header-section-number">1.12</span> 数值得整熟次方</h2>
<p><strong>题目描述</strong></p>
<p>给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。</p>
<p>保证base和exponent不同时为0</p>
<p>实现底层得pow，限制条件多，但是不难得，京东一面其中一个算法题</p>
<div class="sourceCode" id="cb13"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb13-1"><a href="#cb13-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb13-2"><a href="#cb13-2"></a>class Solution<span class="op">:</span></span>
<span id="cb13-3"><a href="#cb13-3"></a><span class="st">    </span>def <span class="kw">Power</span>(self, base, exponent)<span class="op">:</span></span>
<span id="cb13-4"><a href="#cb13-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb13-5"><a href="#cb13-5"></a><span class="st">        </span>temp =<span class="st"> </span>base</span>
<span id="cb13-6"><a href="#cb13-6"></a>        <span class="co"># 0的0次方和0的负数次方无意义</span></span>
<span id="cb13-7"><a href="#cb13-7"></a>        <span class="cf">if</span> base <span class="op">==</span><span class="st"> </span><span class="fl">0.0</span> and exponent <span class="op">&lt;=</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb13-8"><a href="#cb13-8"></a><span class="st">            </span>return None</span>
<span id="cb13-9"><a href="#cb13-9"></a>        <span class="co">#0的次方为0</span></span>
<span id="cb13-10"><a href="#cb13-10"></a>        <span class="cf">if</span> base <span class="op">==</span><span class="st"> </span><span class="fl">0.0</span> <span class="op">:</span></span>
<span id="cb13-11"><a href="#cb13-11"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb13-12"><a href="#cb13-12"></a>        <span class="co">#除0以外的任何数的0次方都为0</span></span>
<span id="cb13-13"><a href="#cb13-13"></a>        <span class="cf">if</span> exponent <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb13-14"><a href="#cb13-14"></a><span class="st">            </span>return <span class="dv">1</span></span>
<span id="cb13-15"><a href="#cb13-15"></a>        <span class="co">#负数次方时</span></span>
<span id="cb13-16"><a href="#cb13-16"></a>        <span class="cf">if</span> exponent <span class="op">&lt;</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb13-17"><a href="#cb13-17"></a><span class="st">            </span><span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="op">-</span>exponent<span class="dv">-1</span>)<span class="op">:</span></span>
<span id="cb13-18"><a href="#cb13-18"></a><span class="st">                </span>base <span class="op">*</span><span class="er">=</span><span class="st"> </span>temp</span>
<span id="cb13-19"><a href="#cb13-19"></a>            return <span class="fl">1.0</span> <span class="op">/</span><span class="st"> </span>base</span>
<span id="cb13-20"><a href="#cb13-20"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb13-21"><a href="#cb13-21"></a><span class="st">            </span><span class="co">#正数次方时</span></span>
<span id="cb13-22"><a href="#cb13-22"></a><span class="st">            </span><span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(exponent<span class="dv">-1</span>)<span class="op">:</span></span>
<span id="cb13-23"><a href="#cb13-23"></a><span class="st">                </span>base <span class="op">*</span><span class="er">=</span><span class="st"> </span>temp</span>
<span id="cb13-24"><a href="#cb13-24"></a>            return base</span></code></pre></div>
<p>今天贝壳找房得笔试挂了，因此多来三个题平复下心情~</p>
<p>算法虐我千百遍我待算法如初恋~</p>
</div>
<div id="调整数组顺序使其位于整熟前面" class="section level2">
<h2><span class="header-section-number">1.13</span> 调整数组顺序使其位于整熟前面</h2>
<p><strong>题目描述</strong></p>
<p>输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。</p>
<p>给一个常规得解法</p>
<div class="sourceCode" id="cb14"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb14-1"><a href="#cb14-1"></a>class Solution<span class="op">:</span></span>
<span id="cb14-2"><a href="#cb14-2"></a><span class="st">    </span>def <span class="kw">reOrderArray</span>(self, array)<span class="op">:</span></span>
<span id="cb14-3"><a href="#cb14-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb14-4"><a href="#cb14-4"></a><span class="st">        </span>j=[]</span>
<span id="cb14-5"><a href="#cb14-5"></a>        o=[]</span>
<span id="cb14-6"><a href="#cb14-6"></a>        <span class="cf">for</span> i <span class="cf">in</span> array<span class="op">:</span></span>
<span id="cb14-7"><a href="#cb14-7"></a><span class="st">            </span><span class="cf">if</span> i%<span class="dv">2</span><span class="op">==</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb14-8"><a href="#cb14-8"></a><span class="st">                </span><span class="kw">o.append</span>(i)</span>
<span id="cb14-9"><a href="#cb14-9"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb14-10"><a href="#cb14-10"></a><span class="st">                </span><span class="kw">j.append</span>(i)</span>
<span id="cb14-11"><a href="#cb14-11"></a>        return j<span class="op">+</span>o</span>
<span id="cb14-12"><a href="#cb14-12"></a>        </span></code></pre></div>
</div>
<div id="链表的倒数第k个节点" class="section level2">
<h2><span class="header-section-number">1.14</span> 链表的倒数第k个节点</h2>
<p>题目描述
输入一个链表，输出该链表中倒数第k个结点。</p>
<p>用一个最直观的方法，时间复杂度为o（k)</p>
<div class="sourceCode" id="cb15"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb15-1"><a href="#cb15-1"></a></span>
<span id="cb15-2"><a href="#cb15-2"></a>class Solution<span class="op">:</span></span>
<span id="cb15-3"><a href="#cb15-3"></a><span class="st">    </span>def <span class="kw">FindKthToTail</span>(self, head, k)<span class="op">:</span></span>
<span id="cb15-4"><a href="#cb15-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb15-5"><a href="#cb15-5"></a><span class="st">        </span><span class="co">#哎，你就把链表当一个list去遍历呗,只是向下移动的方式是不一样的</span></span>
<span id="cb15-6"><a href="#cb15-6"></a><span class="st">        </span>res=[]</span>
<span id="cb15-7"><a href="#cb15-7"></a>        <span class="cf">while</span> head<span class="op">:</span></span>
<span id="cb15-8"><a href="#cb15-8"></a><span class="st">            </span><span class="kw">res.append</span>(head)</span>
<span id="cb15-9"><a href="#cb15-9"></a>            head=head.next</span>
<span id="cb15-10"><a href="#cb15-10"></a>        <span class="cf">if</span> k<span class="op">&gt;</span><span class="kw">len</span>(res) or k<span class="op">&lt;</span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb15-11"><a href="#cb15-11"></a><span class="st">            </span>return </span>
<span id="cb15-12"><a href="#cb15-12"></a>        return res[<span class="op">-</span>k]</span>
<span id="cb15-13"><a href="#cb15-13"></a>        </span></code></pre></div>
</div>
<div id="反转链表" class="section level2">
<h2><span class="header-section-number">1.15</span> 反转链表</h2>
<p><strong>题目描述</strong>
输入一个链表，反转链表后，输出新链表的表头。</p>
<p>自己画个图就非常的明白了</p>
<div class="sourceCode" id="cb16"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb16-1"><a href="#cb16-1"></a>class Solution<span class="op">:</span></span>
<span id="cb16-2"><a href="#cb16-2"></a><span class="st">    </span><span class="co"># 返回ListNode</span></span>
<span id="cb16-3"><a href="#cb16-3"></a><span class="st">    </span>def <span class="kw">ReverseList</span>(self, pHead)<span class="op">:</span></span>
<span id="cb16-4"><a href="#cb16-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb16-5"><a href="#cb16-5"></a><span class="st">        </span></span>
<span id="cb16-6"><a href="#cb16-6"></a><span class="st">        </span>p =<span class="st"> </span>None</span>
<span id="cb16-7"><a href="#cb16-7"></a>        <span class="cf">while</span> pHead<span class="op">:</span></span>
<span id="cb16-8"><a href="#cb16-8"></a><span class="st">            </span>curr=pHead</span>
<span id="cb16-9"><a href="#cb16-9"></a>            pHead=pHead.next</span>
<span id="cb16-10"><a href="#cb16-10"></a>            curr.next=p</span>
<span id="cb16-11"><a href="#cb16-11"></a>            p=curr</span>
<span id="cb16-12"><a href="#cb16-12"></a>        return p</span></code></pre></div>
<p>突然发现，今天笔试题不会的原因是因为，比较重要的5个排序没有学透！！</p>
</div>
<div id="合并两个有序链表" class="section level2">
<h2><span class="header-section-number">1.16</span> 合并两个有序链表</h2>
<p><strong>题目描述</strong>
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。</p>
<div class="sourceCode" id="cb17"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb17-1"><a href="#cb17-1"></a></span>
<span id="cb17-2"><a href="#cb17-2"></a>class Solution<span class="op">:</span></span>
<span id="cb17-3"><a href="#cb17-3"></a><span class="st">    </span><span class="co"># 返回合并后列表</span></span>
<span id="cb17-4"><a href="#cb17-4"></a><span class="st">    </span>def <span class="kw">Merge</span>(self, pHead1, pHead2)<span class="op">:</span></span>
<span id="cb17-5"><a href="#cb17-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb17-6"><a href="#cb17-6"></a><span class="st">        </span><span class="cf">if</span> not pHead1<span class="op">:</span></span>
<span id="cb17-7"><a href="#cb17-7"></a><span class="st">            </span>return pHead2</span>
<span id="cb17-8"><a href="#cb17-8"></a>        <span class="cf">if</span> not pHead2<span class="op">:</span></span>
<span id="cb17-9"><a href="#cb17-9"></a><span class="st">            </span>return pHead1</span>
<span id="cb17-10"><a href="#cb17-10"></a>        <span class="cf">if</span> pHead1.val<span class="op">&lt;</span>pHead2.val<span class="op">:</span></span>
<span id="cb17-11"><a href="#cb17-11"></a><span class="st">            </span>pHead1.next =<span class="st"> </span><span class="kw">self.Merge</span>(pHead1.next,pHead2)</span>
<span id="cb17-12"><a href="#cb17-12"></a>            return pHead1</span>
<span id="cb17-13"><a href="#cb17-13"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb17-14"><a href="#cb17-14"></a><span class="st">            </span>pHead2.next =<span class="st"> </span><span class="kw">self.Merge</span>(pHead1,pHead2.next)</span>
<span id="cb17-15"><a href="#cb17-15"></a>            return pHead2</span></code></pre></div>
</div>
<div id="树的子结构" class="section level2">
<h2><span class="header-section-number">1.17</span> 树的子结构</h2>
<p><strong>题目描述</strong></p>
<p>输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）</p>
<p>把树看作一个链表的问题呗</p>
</div>
<div id="二叉树的镜像" class="section level2">
<h2><span class="header-section-number">1.18</span> 二叉树的镜像</h2>
<p>题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/<br />
6 10
/   /<br />
5 7 9 11
镜像二叉树
8
/<br />
10 6
/   /<br />
11 9 7 5</p>
<p>思路：观察镜像的特点即可</p>
<div class="sourceCode" id="cb18"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb18-1"><a href="#cb18-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb18-2"><a href="#cb18-2"></a>class TreeNode<span class="op">:</span></span>
<span id="cb18-3"><a href="#cb18-3"></a><span class="st">     </span>def <span class="kw">__init__</span>(self, x)<span class="op">:</span></span>
<span id="cb18-4"><a href="#cb18-4"></a><span class="st">        </span>self.val =<span class="st"> </span>x</span>
<span id="cb18-5"><a href="#cb18-5"></a>        self.left =<span class="st"> </span>None</span>
<span id="cb18-6"><a href="#cb18-6"></a>        self.right =<span class="st"> </span>None</span>
<span id="cb18-7"><a href="#cb18-7"></a> </span>
<span id="cb18-8"><a href="#cb18-8"></a>class Solution<span class="op">:</span></span>
<span id="cb18-9"><a href="#cb18-9"></a><span class="st">    </span><span class="co"># 返回镜像树的根节点</span></span>
<span id="cb18-10"><a href="#cb18-10"></a><span class="st">    </span>def <span class="kw">Mirror</span>(self, root)<span class="op">:</span></span>
<span id="cb18-11"><a href="#cb18-11"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb18-12"><a href="#cb18-12"></a><span class="st">        </span><span class="cf">if</span> not root<span class="op">:</span></span>
<span id="cb18-13"><a href="#cb18-13"></a><span class="st">            </span>return </span>
<span id="cb18-14"><a href="#cb18-14"></a>        root.left,root.right =root.right,root.left</span>
<span id="cb18-15"><a href="#cb18-15"></a>        <span class="kw">self.Mirror</span>(root.left)</span>
<span id="cb18-16"><a href="#cb18-16"></a>        <span class="kw">self.Mirror</span>(root.right)</span>
<span id="cb18-17"><a href="#cb18-17"></a>        return root</span></code></pre></div>
</div>
<div id="顺时针打印矩阵" class="section level2">
<h2><span class="header-section-number">1.19</span> 顺时针打印矩阵</h2>
<p><strong>题目描述</strong>
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.</p>
<p>可以考虑画个图，完事就会想到：每次只取第一行数据，然后再把矩阵逆时针旋转90度</p>
<div class="sourceCode" id="cb19"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb19-1"><a href="#cb19-1"></a></span>
<span id="cb19-2"><a href="#cb19-2"></a>class Solution<span class="op">:</span></span>
<span id="cb19-3"><a href="#cb19-3"></a><span class="st">    </span><span class="co">#每次只取第一行数据，然后再把矩阵逆时针旋转90度</span></span>
<span id="cb19-4"><a href="#cb19-4"></a><span class="st">    </span><span class="co"># matrix类型为二维列表，需要返回列表</span></span>
<span id="cb19-5"><a href="#cb19-5"></a><span class="st">    </span>def <span class="kw">printMatrix</span>(self, matrix)<span class="op">:</span></span>
<span id="cb19-6"><a href="#cb19-6"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb19-7"><a href="#cb19-7"></a><span class="st">        </span>res =<span class="st"> </span>[]</span>
<span id="cb19-8"><a href="#cb19-8"></a>        <span class="cf">while</span> matrix<span class="op">:</span></span>
<span id="cb19-9"><a href="#cb19-9"></a><span class="st">            </span>res <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="kw">matrix.pop</span>(<span class="dv">0</span>)</span>
<span id="cb19-10"><a href="#cb19-10"></a>            matrix =<span class="st"> </span><span class="kw">list</span>(<span class="kw">zip</span>(<span class="op">*</span>matrix))[<span class="op">::-</span><span class="dv">1</span>] <span class="co">#这个转置矩阵的好骚啊！</span></span>
<span id="cb19-11"><a href="#cb19-11"></a>        return res</span></code></pre></div>
</div>
<div id="包含min函数的栈" class="section level2">
<h2><span class="header-section-number">1.20</span> 包含min函数的栈</h2>
<p><strong>题目描述</strong></p>
<p>定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)。</p>
<div class="sourceCode" id="cb20"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb20-1"><a href="#cb20-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb20-2"><a href="#cb20-2"></a>class Solution<span class="op">:</span></span>
<span id="cb20-3"><a href="#cb20-3"></a><span class="st">    </span>def <span class="kw">__init__</span>(self)<span class="op">:</span></span>
<span id="cb20-4"><a href="#cb20-4"></a><span class="st">        </span>self.arr=[]</span>
<span id="cb20-5"><a href="#cb20-5"></a>    def <span class="kw">push</span>(self, node)<span class="op">:</span></span>
<span id="cb20-6"><a href="#cb20-6"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb20-7"><a href="#cb20-7"></a><span class="st">        </span><span class="kw">self.arr.append</span>(node)</span>
<span id="cb20-8"><a href="#cb20-8"></a>    def <span class="kw">pop</span>(self)<span class="op">:</span></span>
<span id="cb20-9"><a href="#cb20-9"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb20-10"><a href="#cb20-10"></a><span class="st">        </span>return <span class="kw">self.arr.pop</span>()</span>
<span id="cb20-11"><a href="#cb20-11"></a>    def <span class="kw">top</span>(self)<span class="op">:</span></span>
<span id="cb20-12"><a href="#cb20-12"></a><span class="st">        </span>return self.arr[<span class="op">-</span><span class="dv">1</span>]</span>
<span id="cb20-13"><a href="#cb20-13"></a>    def <span class="kw">min</span>(self)<span class="op">:</span></span>
<span id="cb20-14"><a href="#cb20-14"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb20-15"><a href="#cb20-15"></a><span class="st">        </span>return <span class="kw">min</span>(self.arr)</span></code></pre></div>
</div>
<div id="栈的压入和弹出顺序" class="section level2">
<h2><span class="header-section-number">1.21</span> 栈的压入和弹出顺序</h2>
<p><strong>题目描述</strong></p>
<p>输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）</p>
<p>思路：题没读明白，直接看的解析</p>
<blockquote>
<p>’’’
首先找到这个规律，判断顺序是否正确，必须先将压入序列全部遍历后，才能进行判断，
即判断的永远是出栈序列的最后两个。
然后就有方法，先将push序列依次压入栈，并判断栈顶元素是否和弹出序列pop的首位相同，
如果相同，则弹出该元素，并且pop首位加一，作为下一个判断位置。如果不相同，则push继续压入。
如果push全部压入，表明这时的弹出顺序已经确定。这时候判断弹出序列pop的首位和栈顶元素是否相同，
不相同，则表明该序列为假。如果全部判断都相同，就为真。</p>
</blockquote>
<p>’’’</p>
<ul>
<li>感觉例子看的有点晕糊，栈的存储原则是后进先出</li>
</ul>
<div class="sourceCode" id="cb21"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb21-1"><a href="#cb21-1"></a>class Solution<span class="op">:</span></span>
<span id="cb21-2"><a href="#cb21-2"></a><span class="st">    </span>def <span class="kw">IsPopOrder</span>(self, pushV, popV)<span class="op">:</span></span>
<span id="cb21-3"><a href="#cb21-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb21-4"><a href="#cb21-4"></a><span class="st">        </span>stack=[]</span>
<span id="cb21-5"><a href="#cb21-5"></a>        <span class="cf">while</span> popV<span class="op">:</span></span>
<span id="cb21-6"><a href="#cb21-6"></a><span class="st">            </span><span class="co">##如果stack的最后一个元素与popV中第一个元素相等，将两个元素都弹出</span></span>
<span id="cb21-7"><a href="#cb21-7"></a><span class="st">            </span><span class="cf">if</span> stack and stack[<span class="op">-</span><span class="dv">1</span>]<span class="op">==</span>popV[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb21-8"><a href="#cb21-8"></a><span class="st">                </span><span class="kw">stack.pop</span>()</span>
<span id="cb21-9"><a href="#cb21-9"></a>                <span class="kw">popV.pop</span>(<span class="dv">0</span>)</span>
<span id="cb21-10"><a href="#cb21-10"></a>            <span class="co"># 如果pushV中有数据，压入stack</span></span>
<span id="cb21-11"><a href="#cb21-11"></a>            elif pushV<span class="op">:</span></span>
<span id="cb21-12"><a href="#cb21-12"></a><span class="st">                </span><span class="kw">stack.append</span>(<span class="kw">pushV.pop</span>(<span class="dv">0</span>))</span>
<span id="cb21-13"><a href="#cb21-13"></a>            <span class="co"># 上面情况都不满足，直接返回false。</span></span>
<span id="cb21-14"><a href="#cb21-14"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb21-15"><a href="#cb21-15"></a><span class="st">                </span>return False</span>
<span id="cb21-16"><a href="#cb21-16"></a>        return True</span>
<span id="cb21-17"><a href="#cb21-17"></a>        </span></code></pre></div>
</div>
<div id="最小的k个数" class="section level2">
<h2><span class="header-section-number">1.22</span> 最小的K个数</h2>
<p><strong>题目描述</strong>
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。</p>
<div class="sourceCode" id="cb22"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb22-1"><a href="#cb22-1"></a>class Solution<span class="op">:</span></span>
<span id="cb22-2"><a href="#cb22-2"></a><span class="st">    </span>def <span class="kw">GetLeastNumbers_Solution</span>(self, tinput, k)<span class="op">:</span></span>
<span id="cb22-3"><a href="#cb22-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb22-4"><a href="#cb22-4"></a><span class="st">        </span><span class="cf">if</span> tinput<span class="op">==</span>[] or k<span class="op">&gt;</span><span class="kw">len</span>(tinput)<span class="op">:</span></span>
<span id="cb22-5"><a href="#cb22-5"></a><span class="st">            </span>return []</span>
<span id="cb22-6"><a href="#cb22-6"></a>        <span class="kw">tinput.sort</span>()</span>
<span id="cb22-7"><a href="#cb22-7"></a>        return tinput[<span class="op">:</span>k]</span></code></pre></div>
</div>
<div id="最大子序和" class="section level2">
<h2><span class="header-section-number">1.23</span> 最大子序和</h2>
<p><strong>题目描述</strong>
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)</p>
<p>典型的动态规划</p>
<div class="sourceCode" id="cb23"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb23-1"><a href="#cb23-1"></a>class Solution<span class="op">:</span></span>
<span id="cb23-2"><a href="#cb23-2"></a><span class="st">    </span>def <span class="kw">FindGreatestSumOfSubArray</span>(self, array)<span class="op">:</span></span>
<span id="cb23-3"><a href="#cb23-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb23-4"><a href="#cb23-4"></a><span class="st">        </span>n=<span class="kw">len</span>(array)</span>
<span id="cb23-5"><a href="#cb23-5"></a>        <span class="cf">if</span> not array<span class="op">:</span></span>
<span id="cb23-6"><a href="#cb23-6"></a><span class="st">            </span>return </span>
<span id="cb23-7"><a href="#cb23-7"></a>        <span class="cf">if</span> <span class="kw">len</span>(array)<span class="op">==</span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb23-8"><a href="#cb23-8"></a><span class="st">            </span>return array[<span class="op">-</span><span class="dv">1</span>]</span>
<span id="cb23-9"><a href="#cb23-9"></a>        dp=[<span class="dv">0</span>]<span class="op">*</span>n</span>
<span id="cb23-10"><a href="#cb23-10"></a>        dp[<span class="dv">0</span>]=array[<span class="dv">0</span>]</span>
<span id="cb23-11"><a href="#cb23-11"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>,n)<span class="op">:</span></span>
<span id="cb23-12"><a href="#cb23-12"></a><span class="st">            </span>dp[i]=<span class="kw">max</span>(dp[i<span class="dv">-1</span>]<span class="op">+</span>array[i],array[i])</span>
<span id="cb23-13"><a href="#cb23-13"></a>        return <span class="kw">max</span>(dp)</span></code></pre></div>
</div>
<div id="数组中出现次数超过一半的数字" class="section level2">
<h2><span class="header-section-number">1.24</span> 数组中出现次数超过一半的数字</h2>
<p><strong>题目描述</strong>
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。</p>
<p>给出两种解法</p>
<div class="sourceCode" id="cb24"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb24-1"><a href="#cb24-1"></a></span>
<span id="cb24-2"><a href="#cb24-2"></a><span class="co"># 数量超过数组长度一半的数字排序后必定占据中间位置</span></span>
<span id="cb24-3"><a href="#cb24-3"></a>class Solution<span class="op">:</span></span>
<span id="cb24-4"><a href="#cb24-4"></a><span class="st">    </span>def <span class="kw">MoreThanHalfNum_Solution</span>(self, numbers)<span class="op">:</span></span>
<span id="cb24-5"><a href="#cb24-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb24-6"><a href="#cb24-6"></a><span class="st">        </span><span class="kw">numbers.sort</span>()</span>
<span id="cb24-7"><a href="#cb24-7"></a>        theone =<span class="st"> </span>numbers[<span class="kw">len</span>(numbers)<span class="op">/</span><span class="dv">2</span>]</span>
<span id="cb24-8"><a href="#cb24-8"></a>        <span class="cf">if</span> <span class="kw">numbers.count</span>(theone) <span class="op">&gt;</span><span class="st"> </span><span class="kw">len</span>(numbers)<span class="op">/</span><span class="dv">2</span><span class="op">:</span></span>
<span id="cb24-9"><a href="#cb24-9"></a><span class="st">            </span>return theone</span>
<span id="cb24-10"><a href="#cb24-10"></a>        return  <span class="dv">0</span></span></code></pre></div>
<div class="sourceCode" id="cb25"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb25-1"><a href="#cb25-1"></a>class Solution<span class="op">:</span></span>
<span id="cb25-2"><a href="#cb25-2"></a><span class="st">    </span>def <span class="kw">MoreThanHalfNum_Solution</span>(self, numbers)<span class="op">:</span></span>
<span id="cb25-3"><a href="#cb25-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb25-4"><a href="#cb25-4"></a><span class="st">        </span>A =<span class="st"> </span>{}</span>
<span id="cb25-5"><a href="#cb25-5"></a>        <span class="cf">for</span> i <span class="cf">in</span> numbers<span class="op">:</span></span>
<span id="cb25-6"><a href="#cb25-6"></a><span class="st">            </span><span class="cf">if</span> i <span class="cf">in</span> A<span class="op">:</span></span>
<span id="cb25-7"><a href="#cb25-7"></a><span class="st">                </span>A[i] <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb25-8"><a href="#cb25-8"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb25-9"><a href="#cb25-9"></a><span class="st">                </span>A[i] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb25-10"><a href="#cb25-10"></a>        maxnum =<span class="st"> </span><span class="kw">max</span>(<span class="kw">A.values</span>())</span>
<span id="cb25-11"><a href="#cb25-11"></a>        <span class="kw">print</span>(maxnum)</span>
<span id="cb25-12"><a href="#cb25-12"></a>        <span class="cf">if</span> <span class="dv">2</span><span class="op">*</span>maxnum <span class="op">&gt;</span><span class="st"> </span><span class="kw">len</span>(numbers)<span class="op">:</span></span>
<span id="cb25-13"><a href="#cb25-13"></a><span class="st">            </span>return [k <span class="cf">for</span> k,v <span class="cf">in</span> <span class="kw">A.items</span>() <span class="cf">if</span> v<span class="op">==</span><span class="st"> </span><span class="kw">max</span>(<span class="kw">A.values</span>())][<span class="dv">0</span>]</span>
<span id="cb25-14"><a href="#cb25-14"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb25-15"><a href="#cb25-15"></a><span class="st">            </span>return <span class="dv">0</span></span></code></pre></div>
</div>
<div id="字符串的排序" class="section level2">
<h2><span class="header-section-number">1.25</span> 字符串的排序</h2>
<p>这个题是腾讯今年的笔试题之一</p>
<p><strong>题目描述</strong>
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。</p>
<p>先给一个能调包做的</p>
<p>itertools.permutations 通俗地讲，就是返回可迭代对象的所有数学全排列方式。</p>
<div class="sourceCode" id="cb26"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb26-1"><a href="#cb26-1"></a><span class="co">#Python中的itertools.permutations,返回可迭代对象的所有数学全排列方式。</span></span>
<span id="cb26-2"><a href="#cb26-2"></a><span class="co">#join()方法用于将序列中的元素以指定的字符连接生成一个新的字符串。</span></span>
<span id="cb26-3"><a href="#cb26-3"></a><span class="co">#set()函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。</span></span>
<span id="cb26-4"><a href="#cb26-4"></a><span class="co">#sort()函数用于对原列表进行排序，如果指定参数，则使用比较函数指定的比较函数</span></span>
<span id="cb26-5"><a href="#cb26-5"></a><span class="co">#list()方法用于将元组转换为列表。</span></span></code></pre></div>
<div class="sourceCode" id="cb27"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb27-1"><a href="#cb27-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb27-2"><a href="#cb27-2"></a>import itertools</span>
<span id="cb27-3"><a href="#cb27-3"></a>class Solution<span class="op">:</span></span>
<span id="cb27-4"><a href="#cb27-4"></a><span class="st">    </span>def <span class="kw">Permutation</span>(self, ss)<span class="op">:</span></span>
<span id="cb27-5"><a href="#cb27-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb27-6"><a href="#cb27-6"></a><span class="st">        </span><span class="cf">if</span> not ss<span class="op">:</span></span>
<span id="cb27-7"><a href="#cb27-7"></a><span class="st">            </span>return ss</span>
<span id="cb27-8"><a href="#cb27-8"></a>        result=[]</span>
<span id="cb27-9"><a href="#cb27-9"></a>        k=<span class="kw">itertools.permutations</span>(ss)</span>
<span id="cb27-10"><a href="#cb27-10"></a>        <span class="cf">for</span> i <span class="cf">in</span> k<span class="op">:</span></span>
<span id="cb27-11"><a href="#cb27-11"></a><span class="st">            </span><span class="kw">result.append</span>(<span class="st">&#39;&#39;</span><span class="kw">.join</span>(i))</span>
<span id="cb27-12"><a href="#cb27-12"></a>        result=<span class="kw">list</span>(<span class="kw">set</span>(result))</span>
<span id="cb27-13"><a href="#cb27-13"></a>        <span class="kw">result.sort</span>()</span>
<span id="cb27-14"><a href="#cb27-14"></a>        return result</span>
<span id="cb27-15"><a href="#cb27-15"></a>        </span></code></pre></div>
<p><strong>方法二</strong></p>
<div class="sourceCode" id="cb28"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb28-1"><a href="#cb28-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb28-2"><a href="#cb28-2"></a>class Solution<span class="op">:</span></span>
<span id="cb28-3"><a href="#cb28-3"></a><span class="st">    </span>def <span class="kw">Permutation</span>(self, ss)<span class="op">:</span></span>
<span id="cb28-4"><a href="#cb28-4"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(ss) <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb28-5"><a href="#cb28-5"></a><span class="st">            </span>return []</span>
<span id="cb28-6"><a href="#cb28-6"></a>        res =<span class="st"> </span>[ss[<span class="dv">0</span>]]</span>
<span id="cb28-7"><a href="#cb28-7"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>, <span class="kw">len</span>(ss))<span class="op">:</span></span>
<span id="cb28-8"><a href="#cb28-8"></a><span class="st">            </span>tmp_list =<span class="st"> </span>res</span>
<span id="cb28-9"><a href="#cb28-9"></a>            res =<span class="st"> </span>[]</span>
<span id="cb28-10"><a href="#cb28-10"></a>            <span class="cf">for</span> item <span class="cf">in</span> tmp_list<span class="op">:</span></span>
<span id="cb28-11"><a href="#cb28-11"></a><span class="st">                </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(item)<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb28-12"><a href="#cb28-12"></a><span class="st">                    </span>new_item =<span class="st"> </span>item[<span class="op">:</span>j] <span class="op">+</span><span class="st"> </span>ss[i] <span class="op">+</span><span class="st"> </span>item[j<span class="op">:</span>]</span>
<span id="cb28-13"><a href="#cb28-13"></a>                    <span class="kw">res.append</span>(new_item)</span>
<span id="cb28-14"><a href="#cb28-14"></a>        result =<span class="st"> </span><span class="kw">list</span>(<span class="kw">set</span>(res))</span>
<span id="cb28-15"><a href="#cb28-15"></a>        <span class="kw">result.sort</span>()</span>
<span id="cb28-16"><a href="#cb28-16"></a>        return result</span></code></pre></div>
<p><strong>b站笔试题</strong></p>
</div>
<div id="有效的括号" class="section level2">
<h2><span class="header-section-number">1.26</span> 有效的括号</h2>
<p>题目描述：</p>
<p>给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，’]’ 的字符串，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<p>左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。</p>
<p>示例 1:</p>
<p>输入: “()”
输出: true
示例 2:</p>
<p>输入: “()<span></span>”
输出: true
示例 3:</p>
<p>输入: “(]”
输出: false
示例 4:</p>
<p>输入: “([)]”
输出: false
示例 5:</p>
<p>输入: “{[]}”
输出: true</p>
<p>知识点：栈</p>
<p><strong>解题思路</strong>
当开始接触题目时，我们会不禁想到如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同, 会不会就是有效的括号了呢?
事实上不是的，假如输入是 [ (] ) ，每种括号的左右数量分别相等, 但不是有效的括号。这是因为结果还与括号 的位置有关。
仔细分析我们发现，对于有效的括号, 它的部分子表达式仍然是有效的括号, 比如 <span class="math inline">\(\quad\{()[()]\}\)</span> 是一个有效的括 号, <span class="math inline">\(\quad()[\{\}]\)</span> 是有效的括号, <span class="math inline">\(\quad[()]\)</span> 也是有效的括号。并且当我们<strong>每次删除一个最小的括号对时，我们会逐渐将 括号删除完</strong>。比如下面的例子。</p>
<p><img src="figs/khao.png" /></p>
<p>这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈，当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。</p>
<p>代码中我们使用了哈希表来判断是否能够形成括号，从而决定进行入栈操作还是出栈操作。<a href="https://leetcode-cn.com/problems/valid-parentheses/solution/zhu-bu-fen-xi-tu-jie-zhan-zhan-shi-zui-biao-zhun-d/">leetcode</a></p>
<ul>
<li>使用栈，是左括号代表入栈，是右括号代表出栈</li>
<li>如果要出栈，出栈的元素要与当前元素匹配</li>
<li>最终栈要为空</li>
</ul>
<div class="sourceCode" id="cb29"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb29-1"><a href="#cb29-1"></a>class Solution<span class="op">:</span></span>
<span id="cb29-2"><a href="#cb29-2"></a><span class="st">    </span>def <span class="kw">isValid</span>(self, s<span class="op">:</span><span class="st"> </span>str) -&gt;<span class="st"> </span>bool<span class="op">:</span></span>
<span id="cb29-3"><a href="#cb29-3"></a><span class="st">        </span>stack=[]                            <span class="co">#设置一个列表，把该列表当做栈来使用即可。</span></span>
<span id="cb29-4"><a href="#cb29-4"></a>        dic={<span class="st">&#39;)&#39;</span><span class="op">:</span><span class="st">&#39;(&#39;</span>,<span class="st">&#39;}&#39;</span><span class="op">:</span><span class="st">&#39;{&#39;</span>,<span class="st">&#39;]&#39;</span><span class="op">:</span><span class="st">&#39;[&#39;</span>}       <span class="co">#使用字典存储括号,并且右括号为key,左括号为value</span></span>
<span id="cb29-5"><a href="#cb29-5"></a>        <span class="cf">for</span> char <span class="cf">in</span> s<span class="op">:</span></span>
<span id="cb29-6"><a href="#cb29-6"></a><span class="st">            </span><span class="cf">if</span> char <span class="cf">in</span> <span class="kw">dic.values</span>()<span class="op">:</span><span class="st">        </span><span class="co">#左括号就入栈</span></span>
<span id="cb29-7"><a href="#cb29-7"></a><span class="st">                </span><span class="kw">stack.append</span>(char)</span>
<span id="cb29-8"><a href="#cb29-8"></a>            elif char <span class="cf">in</span> <span class="kw">dic.keys</span>()<span class="op">:</span><span class="st">        </span><span class="co">#有右括号的话就进行比较，</span></span>
<span id="cb29-9"><a href="#cb29-9"></a><span class="st">                </span><span class="cf">if</span> stack<span class="op">==</span>[] or dic[char] <span class="op">!=</span><span class="st"> </span><span class="kw">stack.pop</span>()<span class="op">:</span></span>
<span id="cb29-10"><a href="#cb29-10"></a><span class="st">                    </span>return False</span>
<span id="cb29-11"><a href="#cb29-11"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb29-12"><a href="#cb29-12"></a><span class="st">                </span>return False                <span class="co">#不再字典中的输入直接输出错误</span></span>
<span id="cb29-13"><a href="#cb29-13"></a></span>
<span id="cb29-14"><a href="#cb29-14"></a>        return stack<span class="op">==</span>[]</span></code></pre></div>
<p>一个比较骚的题解</p>
<div class="sourceCode" id="cb30"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb30-1"><a href="#cb30-1"></a>class Solution<span class="op">:</span></span>
<span id="cb30-2"><a href="#cb30-2"></a><span class="st">    </span>def <span class="kw">isValid</span>(self, s)<span class="op">:</span></span>
<span id="cb30-3"><a href="#cb30-3"></a><span class="st">        </span><span class="cf">while</span> <span class="st">&#39;{}&#39;</span> <span class="cf">in</span> s or <span class="st">&#39;()&#39;</span> <span class="cf">in</span> s or <span class="st">&#39;[]&#39;</span> <span class="cf">in</span> s<span class="op">:</span></span>
<span id="cb30-4"><a href="#cb30-4"></a><span class="st">            </span>s =<span class="st"> </span><span class="kw">s.replace</span>(<span class="st">&#39;{}&#39;</span>, <span class="st">&#39;&#39;</span>)</span>
<span id="cb30-5"><a href="#cb30-5"></a>            s =<span class="st"> </span><span class="kw">s.replace</span>(<span class="st">&#39;[]&#39;</span>, <span class="st">&#39;&#39;</span>)</span>
<span id="cb30-6"><a href="#cb30-6"></a>            s =<span class="st"> </span><span class="kw">s.replace</span>(<span class="st">&#39;()&#39;</span>, <span class="st">&#39;&#39;</span>)</span>
<span id="cb30-7"><a href="#cb30-7"></a>        return s <span class="op">==</span><span class="st"> &#39;&#39;</span></span></code></pre></div>
</div>
<div id="找零" class="section level2">
<h2><span class="header-section-number">1.27</span> 找零</h2>
<p>链接：<a href="https://www.nowcoder.com/questionTerminal/944e5ca0ea88471fbfa73061ebe95728" class="uri">https://www.nowcoder.com/questionTerminal/944e5ca0ea88471fbfa73061ebe95728</a>
来源：牛客网</p>
<p>Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N (0 &lt; N 1024)N(0&lt;N≤1024)的商品，请问最少他会收到多少硬币？</p>
<p>也就是买柠檬水找钱的问题</p>
<div class="sourceCode" id="cb31"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb31-1"><a href="#cb31-1"></a>def <span class="kw">zl</span>(n)<span class="op">:</span></span>
<span id="cb31-2"><a href="#cb31-2"></a><span class="st">    </span>coins=[<span class="dv">1</span>,<span class="dv">4</span>,<span class="dv">16</span>,<span class="dv">64</span>]</span>
<span id="cb31-3"><a href="#cb31-3"></a>    </span>
<span id="cb31-4"><a href="#cb31-4"></a>    s=<span class="dv">1024</span><span class="op">-</span>n<span class="op">+</span><span class="dv">1</span></span>
<span id="cb31-5"><a href="#cb31-5"></a>    dp=[<span class="dv">1024</span>]<span class="op">*</span>(s)</span>
<span id="cb31-6"><a href="#cb31-6"></a>    dp[<span class="dv">0</span>]=<span class="dv">0</span></span>
<span id="cb31-7"><a href="#cb31-7"></a>    <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>,s)<span class="op">:</span></span>
<span id="cb31-8"><a href="#cb31-8"></a><span class="st">        </span><span class="cf">for</span> c <span class="cf">in</span> coins<span class="op">:</span></span>
<span id="cb31-9"><a href="#cb31-9"></a><span class="st">            </span><span class="cf">if</span> i<span class="op">-</span>c<span class="op">&gt;=</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb31-10"><a href="#cb31-10"></a><span class="st">                </span>dp[i]=<span class="kw">min</span>(dp[i<span class="op">-</span>c]<span class="op">+</span><span class="dv">1</span>,dp[i])</span>
<span id="cb31-11"><a href="#cb31-11"></a>                </span>
<span id="cb31-12"><a href="#cb31-12"></a>    return dp[<span class="op">-</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="点游戏" class="section level2">
<h2><span class="header-section-number">1.28</span> 24点游戏</h2>
<p>你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。</p>
<p>示例 1:</p>
<p>输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:</p>
<p>输入: [1, 2, 1, 2]
输出: False</p>
<p>注意:</p>
<p>除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。</p>
<blockquote>
<p>四个数取出两个数之后,做加减乘除处理之后加入到原数组中会剩下三个数,递归交给下一层去处理<a href="https://leetcode-cn.com/problems/24-game/solution/python-dfsdi-gui-by-akari-5/">akari-5</a></p>
</blockquote>
<div class="sourceCode" id="cb32"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb32-1"><a href="#cb32-1"></a>class Solution<span class="op">:</span></span>
<span id="cb32-2"><a href="#cb32-2"></a><span class="st">    </span>def <span class="kw">judgePoint24</span>(self, nums<span class="op">:</span><span class="st"> </span>List[int]) -&gt;<span class="st"> </span>bool<span class="op">:</span></span>
<span id="cb32-3"><a href="#cb32-3"></a><span class="st">        </span><span class="cf">if</span> not nums<span class="op">:</span><span class="st"> </span>return False</span>
<span id="cb32-4"><a href="#cb32-4"></a>        def <span class="kw">helper</span>(nums)<span class="op">:</span></span>
<span id="cb32-5"><a href="#cb32-5"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">len</span>(nums) <span class="op">==</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span><span class="st"> </span>return <span class="kw">abs</span>(nums[<span class="dv">0</span>]<span class="op">-</span><span class="dv">24</span>) <span class="op">&lt;</span><span class="st"> </span><span class="fl">1e-6</span></span>
<span id="cb32-6"><a href="#cb32-6"></a>            <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(nums))<span class="op">:</span></span>
<span id="cb32-7"><a href="#cb32-7"></a><span class="st">                </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(nums))<span class="op">:</span></span>
<span id="cb32-8"><a href="#cb32-8"></a><span class="st">                    </span><span class="cf">if</span> i <span class="op">!=</span><span class="st"> </span>j<span class="op">:</span></span>
<span id="cb32-9"><a href="#cb32-9"></a><span class="st">                        </span>newnums =<span class="st"> </span>[nums[k] <span class="cf">for</span> k <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(nums)) <span class="cf">if</span> i <span class="op">!=</span><span class="st"> </span>k <span class="op">!=</span><span class="st"> </span>j]</span>
<span id="cb32-10"><a href="#cb32-10"></a>                        <span class="cf">if</span> <span class="kw">helper</span>(newnums <span class="op">+</span><span class="st"> </span>[nums[i]<span class="op">+</span>nums[j]])<span class="op">:</span><span class="st"> </span>return True</span>
<span id="cb32-11"><a href="#cb32-11"></a>                        <span class="cf">if</span> <span class="kw">helper</span>(newnums <span class="op">+</span><span class="st"> </span>[nums[i]<span class="op">-</span>nums[j]])<span class="op">:</span><span class="st"> </span>return True</span>
<span id="cb32-12"><a href="#cb32-12"></a>                        <span class="cf">if</span> <span class="kw">helper</span>(newnums <span class="op">+</span><span class="st"> </span>[nums[i]<span class="op">*</span>nums[j]])<span class="op">:</span><span class="st"> </span>return True</span>
<span id="cb32-13"><a href="#cb32-13"></a>                        <span class="cf">if</span> nums[j] <span class="op">!=</span><span class="st"> </span><span class="dv">0</span> and <span class="kw">helper</span>(newnums <span class="op">+</span><span class="st"> </span>[nums[i]<span class="op">/</span>nums[j]])<span class="op">:</span><span class="st"> </span>return True</span>
<span id="cb32-14"><a href="#cb32-14"></a>            return False</span>
<span id="cb32-15"><a href="#cb32-15"></a>        return <span class="kw">helper</span>(nums)</span></code></pre></div>
</div>
<div id="从上到下打印二叉树" class="section level2">
<h2><span class="header-section-number">1.29</span> 从上到下打印二叉树</h2>
<p><strong>题目描述</strong>
从上往下打印出二叉树的每个节点，同层节点从左至右打印。</p>
<p>思路：二叉树的层次遍历,一层一层遍历完继续下一层</p>
<div class="sourceCode" id="cb33"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb33-1"><a href="#cb33-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb33-2"><a href="#cb33-2"></a><span class="co"># class TreeNode:</span></span>
<span id="cb33-3"><a href="#cb33-3"></a>def <span class="kw">__init__</span>(self, x)<span class="op">:</span></span>
<span id="cb33-4"><a href="#cb33-4"></a><span class="st">        </span>self.val =<span class="st"> </span>x</span>
<span id="cb33-5"><a href="#cb33-5"></a>        self.left =<span class="st"> </span>None</span>
<span id="cb33-6"><a href="#cb33-6"></a>        self.right =<span class="st"> </span>None</span>
<span id="cb33-7"><a href="#cb33-7"></a>class Solution<span class="op">:</span></span>
<span id="cb33-8"><a href="#cb33-8"></a><span class="st">    </span><span class="co"># 返回从上到下每个节点值列表，例：[1,2,3]</span></span>
<span id="cb33-9"><a href="#cb33-9"></a><span class="st">    </span>def <span class="kw">PrintFromTopToBottom</span>(self, root)<span class="op">:</span></span>
<span id="cb33-10"><a href="#cb33-10"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb33-11"><a href="#cb33-11"></a><span class="st">        </span><span class="co">#</span></span>
<span id="cb33-12"><a href="#cb33-12"></a><span class="st">        </span><span class="cf">if</span> not root<span class="op">:</span></span>
<span id="cb33-13"><a href="#cb33-13"></a><span class="st">            </span>return <span class="st">&#39;&#39;</span></span>
<span id="cb33-14"><a href="#cb33-14"></a>        </span>
<span id="cb33-15"><a href="#cb33-15"></a>        que=[root] <span class="co">#根节点保存在队列中</span></span>
<span id="cb33-16"><a href="#cb33-16"></a>        res=[] <span class="co">#用一个list保存输出值</span></span>
<span id="cb33-17"><a href="#cb33-17"></a>        <span class="cf">while</span> que<span class="op">:</span></span>
<span id="cb33-18"><a href="#cb33-18"></a><span class="st">            </span><span class="cf">if</span> que[<span class="dv">0</span>].left<span class="op">:</span></span>
<span id="cb33-19"><a href="#cb33-19"></a><span class="st">                </span><span class="kw">que.append</span>(que[<span class="dv">0</span>].left)</span>
<span id="cb33-20"><a href="#cb33-20"></a>            <span class="cf">if</span> que[<span class="dv">0</span>].right<span class="op">:</span></span>
<span id="cb33-21"><a href="#cb33-21"></a><span class="st">                </span><span class="kw">que.append</span>(que[<span class="dv">0</span>].right)</span>
<span id="cb33-22"><a href="#cb33-22"></a>            <span class="kw">res.append</span>(que[<span class="dv">0</span>].val)</span>
<span id="cb33-23"><a href="#cb33-23"></a>            <span class="kw">que.pop</span>(<span class="dv">0</span>) <span class="co">#遍历完一个根和左右就删掉</span></span>
<span id="cb33-24"><a href="#cb33-24"></a>        return res</span>
<span id="cb33-25"><a href="#cb33-25"></a>        </span></code></pre></div>
</div>
<div id="二叉树的后续遍历" class="section level2">
<h2><span class="header-section-number">1.30</span> 二叉树的后续遍历</h2>
<p><strong>题目描述</strong>
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。</p>
<ul>
<li>后序遍历的序列中，最后一个数字是树的根节点 ，</li>
<li>数组中前面的数字可以分为两部分：第一部分是左子树节点的值，都比根节点的值小；</li>
<li>第二部分 是右子树节点的值，都比根节点的值大，</li>
<li>后面用递归分别判断前后两部分 是否符合以上原则。</li>
</ul>
<div class="sourceCode" id="cb34"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb34-1"><a href="#cb34-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb34-2"><a href="#cb34-2"></a>class Solution<span class="op">:</span></span>
<span id="cb34-3"><a href="#cb34-3"></a><span class="st">    </span>def <span class="kw">VerifySquenceOfBST</span>(self, sequence)<span class="op">:</span></span>
<span id="cb34-4"><a href="#cb34-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb34-5"><a href="#cb34-5"></a><span class="st">        </span></span>
<span id="cb34-6"><a href="#cb34-6"></a><span class="st">        </span><span class="cf">if</span> sequence<span class="op">==</span>None or <span class="kw">len</span>(sequence)<span class="op">==</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb34-7"><a href="#cb34-7"></a><span class="st">            </span>return False</span>
<span id="cb34-8"><a href="#cb34-8"></a>        length=<span class="kw">len</span>(sequence)</span>
<span id="cb34-9"><a href="#cb34-9"></a>        root=sequence[length<span class="dv">-1</span>]</span>
<span id="cb34-10"><a href="#cb34-10"></a>        <span class="co"># 在二叉搜索树中 左子树节点小于根节点</span></span>
<span id="cb34-11"><a href="#cb34-11"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(length)<span class="op">:</span></span>
<span id="cb34-12"><a href="#cb34-12"></a><span class="st">            </span><span class="cf">if</span> sequence[i]<span class="op">&gt;</span>root<span class="op">:</span></span>
<span id="cb34-13"><a href="#cb34-13"></a><span class="st">                </span><span class="cf">break</span></span>
<span id="cb34-14"><a href="#cb34-14"></a>        <span class="co"># 二叉搜索树中右子树的节点都大于根节点</span></span>
<span id="cb34-15"><a href="#cb34-15"></a>        <span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(i,length)<span class="op">:</span></span>
<span id="cb34-16"><a href="#cb34-16"></a><span class="st">            </span><span class="cf">if</span> sequence[j]<span class="op">&lt;</span>root<span class="op">:</span></span>
<span id="cb34-17"><a href="#cb34-17"></a><span class="st">                </span>return False</span>
<span id="cb34-18"><a href="#cb34-18"></a>        <span class="co"># 判断左子树是否为二叉树</span></span>
<span id="cb34-19"><a href="#cb34-19"></a>        left=True</span>
<span id="cb34-20"><a href="#cb34-20"></a>        <span class="cf">if</span> i<span class="op">&gt;</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb34-21"><a href="#cb34-21"></a><span class="st">            </span>left=<span class="kw">self.VerifySquenceOfBST</span>(sequence[<span class="dv">0</span><span class="op">:</span>i])</span>
<span id="cb34-22"><a href="#cb34-22"></a>        <span class="co"># 判断 右子树是否为二叉树</span></span>
<span id="cb34-23"><a href="#cb34-23"></a>        right=True</span>
<span id="cb34-24"><a href="#cb34-24"></a>        <span class="cf">if</span> i<span class="op">&lt;</span>length<span class="dv">-1</span><span class="op">:</span></span>
<span id="cb34-25"><a href="#cb34-25"></a><span class="st">            </span>right=<span class="kw">self.VerifySquenceOfBST</span>(sequence[i<span class="op">:-</span><span class="dv">1</span>])</span>
<span id="cb34-26"><a href="#cb34-26"></a>        return left and right</span></code></pre></div>
</div>
<div id="二叉树中和为某一路径值" class="section level2">
<h2><span class="header-section-number">1.31</span> 二叉树中和为某一路径值</h2>
<p><strong>题目描述</strong></p>
<p>输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。</p>
<div class="sourceCode" id="cb35"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb35-1"><a href="#cb35-1"></a>思路是递归：递归方法是返回当前路径下匹配目标值的路径。</span>
<span id="cb35-2"><a href="#cb35-2"></a>目标值 =<span class="st"> </span>目标值 <span class="op">-</span><span class="st"> </span>当前节点值</span>
<span id="cb35-3"><a href="#cb35-3"></a>共有几种情况：</span>
<span id="cb35-4"><a href="#cb35-4"></a>0，当节点为空，return</span>
<span id="cb35-5"><a href="#cb35-5"></a>1，当目标值小于0，return</span>
<span id="cb35-6"><a href="#cb35-6"></a>2，当目标值为0 并且 节点下无其他节点</span>
<span id="cb35-7"><a href="#cb35-7"></a>节点下无其他节点说明是叶子节点，并且路径值的和满足了目标值，添加到结果中  并且return</span>
<span id="cb35-8"><a href="#cb35-8"></a>3，当目标值大于0，继续递归</span></code></pre></div>
<div class="sourceCode" id="cb36"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb36-1"><a href="#cb36-1"></a>class Solution<span class="op">:</span></span>
<span id="cb36-2"><a href="#cb36-2"></a><span class="st">    </span><span class="co"># 返回二维列表，内部每个列表表示找到的路径</span></span>
<span id="cb36-3"><a href="#cb36-3"></a><span class="st">    </span>def <span class="kw">FindPath</span>(self, root, expectNumber)<span class="op">:</span></span>
<span id="cb36-4"><a href="#cb36-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb36-5"><a href="#cb36-5"></a><span class="st">        </span>path =<span class="st"> </span>[]</span>
<span id="cb36-6"><a href="#cb36-6"></a>        res =<span class="st"> </span>[]</span>
<span id="cb36-7"><a href="#cb36-7"></a>        def <span class="kw">dfs</span>(root, sum)<span class="op">:</span></span>
<span id="cb36-8"><a href="#cb36-8"></a><span class="st">            </span><span class="cf">if</span> not root<span class="op">:</span></span>
<span id="cb36-9"><a href="#cb36-9"></a><span class="st">                </span>return</span>
<span id="cb36-10"><a href="#cb36-10"></a>            <span class="kw">path.append</span>(root.val)</span>
<span id="cb36-11"><a href="#cb36-11"></a>            sum <span class="op">-</span><span class="er">=</span><span class="st"> </span>root.val</span>
<span id="cb36-12"><a href="#cb36-12"></a>            <span class="cf">if</span> sum <span class="op">==</span><span class="st"> </span><span class="dv">0</span> and not root.left and not root.right<span class="op">:</span></span>
<span id="cb36-13"><a href="#cb36-13"></a><span class="st">                </span><span class="kw">res.append</span>(path[<span class="op">:</span>])</span>
<span id="cb36-14"><a href="#cb36-14"></a>            <span class="kw">dfs</span>(root.left, sum)</span>
<span id="cb36-15"><a href="#cb36-15"></a>            <span class="kw">dfs</span>(root.right, sum)</span>
<span id="cb36-16"><a href="#cb36-16"></a>            <span class="kw">path.pop</span>()</span>
<span id="cb36-17"><a href="#cb36-17"></a>            </span>
<span id="cb36-18"><a href="#cb36-18"></a>        <span class="kw">dfs</span>(root, expectNumber)</span>
<span id="cb36-19"><a href="#cb36-19"></a>        return res</span></code></pre></div>
<p><strong>仔细去想上面三个题的思路</strong></p>
</div>
<div id="复杂链表的复制" class="section level2">
<h2><span class="header-section-number">1.32</span> 复杂链表的复制</h2>
<p><strong>题目描述</strong>
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）</p>
<p>思路：</p>
<div class="sourceCode" id="cb37"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb37-1"><a href="#cb37-1"></a>class Solution<span class="op">:</span></span>
<span id="cb37-2"><a href="#cb37-2"></a><span class="st">    </span><span class="co"># 返回 RandomListNode</span></span>
<span id="cb37-3"><a href="#cb37-3"></a><span class="st">    </span>def <span class="kw">Clone</span>(self, pHead)<span class="op">:</span></span>
<span id="cb37-4"><a href="#cb37-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb37-5"><a href="#cb37-5"></a><span class="st">        </span><span class="cf">if</span> not pHead<span class="op">:</span></span>
<span id="cb37-6"><a href="#cb37-6"></a><span class="st">            </span>return None</span>
<span id="cb37-7"><a href="#cb37-7"></a>        newp =<span class="st"> </span><span class="kw">RandomListNode</span>(pHead.label)</span>
<span id="cb37-8"><a href="#cb37-8"></a>        newp.random =<span class="st"> </span>pHead.random</span>
<span id="cb37-9"><a href="#cb37-9"></a>        newp.next =<span class="st"> </span><span class="kw">self.Clone</span>(pHead.next)</span>
<span id="cb37-10"><a href="#cb37-10"></a>        return newp</span></code></pre></div>
<p>或者下面这一句也是可以的</p>
<div class="sourceCode" id="cb38"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb38-1"><a href="#cb38-1"></a>return <span class="kw">copy.deepcopy</span>(pHead)</span></code></pre></div>
</div>
<div id="反转单词顺序" class="section level2">
<h2><span class="header-section-number">1.33</span> 反转单词顺序</h2>
<p><strong>题目描述</strong></p>
<p>牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？</p>
<p>能~</p>
<p>字符串的倒序，注意输出的结果表示</p>
<div class="sourceCode" id="cb39"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb39-1"><a href="#cb39-1"></a>class Solution<span class="op">:</span></span>
<span id="cb39-2"><a href="#cb39-2"></a><span class="st">    </span>def <span class="kw">ReverseSentence</span>(self, s)<span class="op">:</span></span>
<span id="cb39-3"><a href="#cb39-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb39-4"><a href="#cb39-4"></a><span class="st">        </span><span class="cf">if</span> not s<span class="op">:</span></span>
<span id="cb39-5"><a href="#cb39-5"></a><span class="st">            </span>return <span class="st">&#39;&#39;</span></span>
<span id="cb39-6"><a href="#cb39-6"></a>        st=<span class="kw">s.split</span>(<span class="st">&#39; &#39;</span>)</span>
<span id="cb39-7"><a href="#cb39-7"></a>        res=st[<span class="op">::-</span><span class="dv">1</span>]</span>
<span id="cb39-8"><a href="#cb39-8"></a>        return <span class="st">&#39; &#39;</span><span class="kw">.join</span>(res)</span></code></pre></div>
</div>
<div id="左旋字符串" class="section level2">
<h2><span class="header-section-number">1.34</span> 左旋字符串</h2>
<p><strong>题目描述</strong>
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！</p>
<div class="sourceCode" id="cb40"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb40-1"><a href="#cb40-1"></a>class Solution<span class="op">:</span></span>
<span id="cb40-2"><a href="#cb40-2"></a><span class="st">    </span>def <span class="kw">LeftRotateString</span>(self, s, n)<span class="op">:</span></span>
<span id="cb40-3"><a href="#cb40-3"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb40-4"><a href="#cb40-4"></a><span class="st">        </span>l=<span class="kw">len</span>(s)</span>
<span id="cb40-5"><a href="#cb40-5"></a>        return s[n<span class="op">:</span>]<span class="op">+</span>s[<span class="op">:</span>n]</span>
<span id="cb40-6"><a href="#cb40-6"></a>        </span></code></pre></div>
</div>
<div id="把数组排成最小整数" class="section level2">
<h2><span class="header-section-number">1.35</span> 把数组排成最小整数</h2>
<p><strong>题目描述</strong>
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。</p>
<p>把数组变成字符串，完事就是常规的冒泡排序就能解决。。冒泡排序的应用</p>
<p>str和int之间的转换，这个需要知道一下</p>
<div class="sourceCode" id="cb41"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb41-1"><a href="#cb41-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb41-2"><a href="#cb41-2"></a>class Solution<span class="op">:</span></span>
<span id="cb41-3"><a href="#cb41-3"></a><span class="st">    </span>def <span class="kw">PrintMinNumber</span>(self, numbers)<span class="op">:</span></span>
<span id="cb41-4"><a href="#cb41-4"></a><span class="st">    </span><span class="co"># write code here</span></span>
<span id="cb41-5"><a href="#cb41-5"></a><span class="st">        </span>n =<span class="st"> </span><span class="kw">len</span>(numbers)</span>
<span id="cb41-6"><a href="#cb41-6"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(n)<span class="op">:</span></span>
<span id="cb41-7"><a href="#cb41-7"></a><span class="st">            </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(i<span class="op">+</span><span class="dv">1</span>, n)<span class="op">:</span></span>
<span id="cb41-8"><a href="#cb41-8"></a><span class="st">                </span><span class="cf">if</span> <span class="kw">int</span>(<span class="kw">str</span>(numbers[i]) <span class="op">+</span><span class="st"> </span><span class="kw">str</span>(numbers[j]) <span class="op">&gt;</span><span class="st"> </span><span class="kw">str</span>(numbers[j]) <span class="op">+</span><span class="st"> </span><span class="kw">str</span>(numbers[i]))<span class="op">:</span></span>
<span id="cb41-9"><a href="#cb41-9"></a><span class="st">                    </span>numbers[j], numbers[i] =<span class="st"> </span>numbers[i], numbers[j]</span>
<span id="cb41-10"><a href="#cb41-10"></a>        return <span class="st">&#39;&#39;</span><span class="kw">.join</span>([<span class="kw">str</span>(i) <span class="cf">for</span> i <span class="cf">in</span> numbers])</span></code></pre></div>
</div>
<div id="丑数" class="section level2">
<h2><span class="header-section-number">1.36</span> 丑数</h2>
<p><strong>题目描述</strong>
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。</p>
<p><strong>思路：</strong>丑数 = 已有的丑数 * (2,3,5) 得到三个新的丑数，但是新的丑数位置不一定正确，切可能会有重复</p>
<p>所以我们每次只新增一个最小值，然后用三个指针记录当前2，3，5质因子形成的最大丑数位置，这样的话就会形成递增的丑数队列，而且遍历的次数也很容易就知道，即n-1,因为1是第一个丑数，n-1次遍历后，我们就可以得到一个含有n个丑数的有序数组，返回最后一个即可。</p>
<div class="sourceCode" id="cb42"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb42-1"><a href="#cb42-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb42-2"><a href="#cb42-2"></a>class Solution<span class="op">:</span></span>
<span id="cb42-3"><a href="#cb42-3"></a><span class="st">    </span>def <span class="kw">GetUglyNumber_Solution</span>(self, index)<span class="op">:</span></span>
<span id="cb42-4"><a href="#cb42-4"></a><span class="st">    </span><span class="co"># write code here</span></span>
<span id="cb42-5"><a href="#cb42-5"></a><span class="st">        </span><span class="cf">if</span> index <span class="op">&lt;=</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb42-6"><a href="#cb42-6"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb42-7"><a href="#cb42-7"></a>        uglyList =<span class="st"> </span>[<span class="dv">1</span>]</span>
<span id="cb42-8"><a href="#cb42-8"></a>        p2 =<span class="st"> </span><span class="dv">0</span> <span class="co"># p2指向小于newUgly且最大的乘以2后可能成为下一个丑数的丑数</span></span>
<span id="cb42-9"><a href="#cb42-9"></a>        p3 =<span class="st"> </span><span class="dv">0</span> <span class="co"># p3指向小于newUgly且最大的乘以3后可能成为下一个丑数的丑数</span></span>
<span id="cb42-10"><a href="#cb42-10"></a>        p5 =<span class="st"> </span><span class="dv">0</span> <span class="co"># p5指向小于newUgly且最大的乘以5后可能成为下一个丑数的丑数</span></span>
<span id="cb42-11"><a href="#cb42-11"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(index<span class="dv">-1</span>)<span class="op">:</span></span>
<span id="cb42-12"><a href="#cb42-12"></a><span class="st">            </span>newUgly =<span class="st"> </span><span class="kw">min</span>(uglyList[p2]<span class="op">*</span><span class="dv">2</span>, uglyList[p3]<span class="op">*</span><span class="dv">3</span>, uglyList[p5]<span class="op">*</span><span class="dv">5</span>)</span>
<span id="cb42-13"><a href="#cb42-13"></a>            <span class="kw">uglyList.append</span>(newUgly)</span>
<span id="cb42-14"><a href="#cb42-14"></a>            <span class="cf">if</span> (newUgly % <span class="dv">2</span> <span class="op">==</span><span class="st"> </span><span class="dv">0</span>)<span class="op">:</span></span>
<span id="cb42-15"><a href="#cb42-15"></a><span class="st">                </span>p2 <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb42-16"><a href="#cb42-16"></a>            <span class="cf">if</span> (newUgly % <span class="dv">3</span> <span class="op">==</span><span class="st"> </span><span class="dv">0</span>)<span class="op">:</span></span>
<span id="cb42-17"><a href="#cb42-17"></a><span class="st">                </span>p3 <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb42-18"><a href="#cb42-18"></a>            <span class="cf">if</span> (newUgly % <span class="dv">5</span> <span class="op">==</span><span class="st"> </span><span class="dv">0</span>)<span class="op">:</span></span>
<span id="cb42-19"><a href="#cb42-19"></a><span class="st">                </span>p5 <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb42-20"><a href="#cb42-20"></a>        return uglyList[<span class="op">-</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="第一个只出现一次的字符串" class="section level2">
<h2><span class="header-section-number">1.37</span> 第一个只出现一次的字符串</h2>
<p><strong>题目描述</strong>
在一个字符串(0&lt;=字符串长度&lt;=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）</p>
<p>简单解法，count计数法</p>
<div class="sourceCode" id="cb43"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb43-1"><a href="#cb43-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb43-2"><a href="#cb43-2"></a>class Solution<span class="op">:</span></span>
<span id="cb43-3"><a href="#cb43-3"></a><span class="st">    </span>def <span class="kw">FirstNotRepeatingChar</span>(self, s)<span class="op">:</span></span>
<span id="cb43-4"><a href="#cb43-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb43-5"><a href="#cb43-5"></a><span class="st">        </span><span class="cf">if</span> not s<span class="op">:</span></span>
<span id="cb43-6"><a href="#cb43-6"></a><span class="st">            </span>return <span class="dv">-1</span></span>
<span id="cb43-7"><a href="#cb43-7"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(s))<span class="op">:</span></span>
<span id="cb43-8"><a href="#cb43-8"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">s.count</span>(s[i]) <span class="op">==</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb43-9"><a href="#cb43-9"></a><span class="st">                </span>return i</span>
<span id="cb43-10"><a href="#cb43-10"></a>        return <span class="dv">-1</span></span></code></pre></div>
<p>或者直接字典</p>
<div class="sourceCode" id="cb44"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb44-1"><a href="#cb44-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb44-2"><a href="#cb44-2"></a>class Solution<span class="op">:</span></span>
<span id="cb44-3"><a href="#cb44-3"></a><span class="st">    </span>def <span class="kw">FirstNotRepeatingChar</span>(self, s)<span class="op">:</span></span>
<span id="cb44-4"><a href="#cb44-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb44-5"><a href="#cb44-5"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(s) <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb44-6"><a href="#cb44-6"></a><span class="st">            </span>return <span class="dv">-1</span></span>
<span id="cb44-7"><a href="#cb44-7"></a>        <span class="cf">for</span> index, value <span class="cf">in</span> <span class="kw">enumerate</span>(s)<span class="op">:</span></span>
<span id="cb44-8"><a href="#cb44-8"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">s.count</span>(value) <span class="op">==</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb44-9"><a href="#cb44-9"></a><span class="st">                </span>return index</span></code></pre></div>
</div>
<div id="数组中的逆序对" class="section level2">
<h2><span class="header-section-number">1.38</span> 数组中的逆序对</h2>
<p><strong>题目描述</strong></p>
<p>在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007</p>
<p>输入描述:
题目保证输入的数组中没有的相同的数字</p>
<p>数据范围：</p>
<p>对于%50的数据,size&lt;=10^4</p>
<p>对于%75的数据,size&lt;=10^5</p>
<p>对于%100的数据,size&lt;=2*10^5</p>
<p>示例1
输入1,2,3,4,5,6,7,0</p>
<p>输出7</p>
<p>思路1：先将原序列排序，然后从排完序的数组中取出最小的，它在原数组中的位置表示有多少比它大的数在它前面，每取出一个在原数组中删除该元素，保证后面取出的元素在原数组中是最小的，这样其位置才能表示有多少比它大的数在它前面，即逆序对数。</p>
<div class="sourceCode" id="cb45"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb45-1"><a href="#cb45-1"></a></span>
<span id="cb45-2"><a href="#cb45-2"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb45-3"><a href="#cb45-3"></a>class Solution<span class="op">:</span></span>
<span id="cb45-4"><a href="#cb45-4"></a><span class="st">    </span>def <span class="kw">InversePairs</span>(self, data)<span class="op">:</span></span>
<span id="cb45-5"><a href="#cb45-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb45-6"><a href="#cb45-6"></a><span class="st">        </span>cnt =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb45-7"><a href="#cb45-7"></a>        copy =<span class="st"> </span>data[<span class="op">:</span>]</span>
<span id="cb45-8"><a href="#cb45-8"></a>        <span class="kw">copy.sort</span>()</span>
<span id="cb45-9"><a href="#cb45-9"></a>        <span class="cf">for</span> i <span class="cf">in</span> copy<span class="op">:</span></span>
<span id="cb45-10"><a href="#cb45-10"></a><span class="st">            </span>cnt <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="kw">data.index</span>(i)</span>
<span id="cb45-11"><a href="#cb45-11"></a>            <span class="kw">data.remove</span>(i)</span>
<span id="cb45-12"><a href="#cb45-12"></a>        return cnt%<span class="dv">1000000007</span></span></code></pre></div>
<p>思路2：归并排序
冒泡排序太暴力了</p>
<p>待我默写出来</p>
</div>
<div id="两个链表的第一个公共节点" class="section level2">
<h2><span class="header-section-number">1.39</span> 两个链表的第一个公共节点</h2>
<p><strong>题目描述</strong></p>
<p>输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）</p>
<p>思路1
如果能从后面遍历两个链表，找到最后一个相同的节点，输出即可。可以利用两个栈来实现。</p>
<div class="sourceCode" id="cb46"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb46-1"><a href="#cb46-1"></a><span class="co">#         self.next = None</span></span>
<span id="cb46-2"><a href="#cb46-2"></a>class Solution<span class="op">:</span></span>
<span id="cb46-3"><a href="#cb46-3"></a><span class="st">    </span>def <span class="kw">FindFirstCommonNode</span>(self, pHead1, pHead2)<span class="op">:</span></span>
<span id="cb46-4"><a href="#cb46-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb46-5"><a href="#cb46-5"></a><span class="st">        </span><span class="cf">if</span> pHead1<span class="op">==</span><span class="st"> </span>None or pHead2 <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb46-6"><a href="#cb46-6"></a><span class="st">            </span>return None</span>
<span id="cb46-7"><a href="#cb46-7"></a>        stack1 =<span class="st"> </span>[]</span>
<span id="cb46-8"><a href="#cb46-8"></a>        stack2 =<span class="st"> </span>[]</span>
<span id="cb46-9"><a href="#cb46-9"></a>        p1 =<span class="st"> </span>pHead1</span>
<span id="cb46-10"><a href="#cb46-10"></a>        <span class="cf">while</span> p1 is not None<span class="op">:</span><span class="st">   </span><span class="co"># 依次将两个链表的所有节点分别压入两个栈中</span></span>
<span id="cb46-11"><a href="#cb46-11"></a><span class="st">            </span><span class="kw">stack1.append</span>(p1)</span>
<span id="cb46-12"><a href="#cb46-12"></a>            p1 =<span class="st"> </span>p1.next</span>
<span id="cb46-13"><a href="#cb46-13"></a>        p2 =<span class="st"> </span>pHead2</span>
<span id="cb46-14"><a href="#cb46-14"></a>        <span class="cf">while</span> p2 is not None<span class="op">:</span></span>
<span id="cb46-15"><a href="#cb46-15"></a><span class="st">            </span><span class="kw">stack2.append</span>(p2)</span>
<span id="cb46-16"><a href="#cb46-16"></a>            p2 =<span class="st"> </span>p2.next</span>
<span id="cb46-17"><a href="#cb46-17"></a>        res =<span class="st"> </span>None</span>
<span id="cb46-18"><a href="#cb46-18"></a>        <span class="cf">while</span> <span class="kw">len</span>(stack1) <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span> and <span class="kw">len</span>(stack2) <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb46-19"><a href="#cb46-19"></a><span class="st">        </span><span class="co"># 从后往前遍历，直到找到两个链表相同的最后一个节点，如果相同的话。</span></span>
<span id="cb46-20"><a href="#cb46-20"></a><span class="st">            </span>v1 =<span class="st"> </span><span class="kw">stack1.pop</span>()</span>
<span id="cb46-21"><a href="#cb46-21"></a>            v2 =<span class="st"> </span><span class="kw">stack2.pop</span>()</span>
<span id="cb46-22"><a href="#cb46-22"></a>            <span class="cf">if</span> v1 <span class="op">==</span><span class="st"> </span>v2<span class="op">:</span></span>
<span id="cb46-23"><a href="#cb46-23"></a><span class="st">                </span>res =<span class="st"> </span>v1</span>
<span id="cb46-24"><a href="#cb46-24"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb46-25"><a href="#cb46-25"></a><span class="st">                </span><span class="cf">break</span></span>
<span id="cb46-26"><a href="#cb46-26"></a>        return res</span></code></pre></div>
<p>下面这个思路好骚啊~<a href="https://blog.csdn.net/ggdhs/article/details/90319403">csdn</a></p>
<p>感觉有点不懂</p>
<p><img src="figs/lbggjd.png" /></p>
<div class="sourceCode" id="cb47"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb47-1"><a href="#cb47-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb47-2"><a href="#cb47-2"></a><span class="co"># class ListNode:</span></span>
<span id="cb47-3"><a href="#cb47-3"></a><span class="co">#     def __init__(self, x):</span></span>
<span id="cb47-4"><a href="#cb47-4"></a><span class="co">#         self.val = x</span></span>
<span id="cb47-5"><a href="#cb47-5"></a><span class="co">#         self.next = None</span></span>
<span id="cb47-6"><a href="#cb47-6"></a>class Solution<span class="op">:</span></span>
<span id="cb47-7"><a href="#cb47-7"></a><span class="st">    </span>def <span class="kw">FindFirstCommonNode</span>(self, pHead1, pHead2)<span class="op">:</span></span>
<span id="cb47-8"><a href="#cb47-8"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb47-9"><a href="#cb47-9"></a><span class="st">        </span><span class="cf">if</span> pHead1<span class="op">==</span><span class="st"> </span>None or pHead2 <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb47-10"><a href="#cb47-10"></a><span class="st">            </span>return None</span>
<span id="cb47-11"><a href="#cb47-11"></a>        p1 =<span class="st"> </span>pHead1</span>
<span id="cb47-12"><a href="#cb47-12"></a>        p2 =<span class="st"> </span>pHead2</span>
<span id="cb47-13"><a href="#cb47-13"></a>        <span class="cf">while</span>(p1<span class="op">!=</span>p2)<span class="op">:</span><span class="st">  </span></span>
<span id="cb47-14"><a href="#cb47-14"></a><span class="st">            </span>p1 =<span class="st"> </span>pHead2 <span class="cf">if</span> p1 is None <span class="cf">else</span> p1.next</span>
<span id="cb47-15"><a href="#cb47-15"></a>            <span class="co"># 由于若pHead2是pHead1的最后一个节点，，因此不能以p1.next==None作为判断条件。</span></span>
<span id="cb47-16"><a href="#cb47-16"></a>            <span class="co"># 否则就会死循环。</span></span>
<span id="cb47-17"><a href="#cb47-17"></a>            p2 =<span class="st"> </span>pHead1 <span class="cf">if</span> p2 is None <span class="cf">else</span> p2.next</span>
<span id="cb47-18"><a href="#cb47-18"></a>        return p1</span></code></pre></div>
</div>
<div id="数字在升序数组中出现的次数" class="section level2">
<h2><span class="header-section-number">1.40</span> 数字在升序数组中出现的次数</h2>
<p><strong>题目描述</strong></p>
<p>统计一个数字在升序数组中出现的次数。</p>
<p>怎么写都能通过吧</p>
<div class="sourceCode" id="cb48"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb48-1"><a href="#cb48-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb48-2"><a href="#cb48-2"></a>class Solution<span class="op">:</span></span>
<span id="cb48-3"><a href="#cb48-3"></a><span class="st">    </span>def <span class="kw">GetNumberOfK</span>(self, data, k)<span class="op">:</span></span>
<span id="cb48-4"><a href="#cb48-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb48-5"><a href="#cb48-5"></a><span class="st">        </span>count =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb48-6"><a href="#cb48-6"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(data))<span class="op">:</span></span>
<span id="cb48-7"><a href="#cb48-7"></a><span class="st">            </span><span class="cf">if</span>(data[i] <span class="op">==</span><span class="st"> </span>k)<span class="op">:</span></span>
<span id="cb48-8"><a href="#cb48-8"></a><span class="st">                </span>count <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb48-9"><a href="#cb48-9"></a>        return count</span>
<span id="cb48-10"><a href="#cb48-10"></a>        <span class="co"># 或者就直接用python的count函数</span></span>
<span id="cb48-11"><a href="#cb48-11"></a>        <span class="co"># return data.count(k)</span></span></code></pre></div>
</div>
<div id="平衡二叉树" class="section level2">
<h2><span class="header-section-number">1.41</span> 平衡二叉树</h2>
<p><strong>题目描述</strong>
输入一棵二叉树，判断该二叉树是否是平衡二叉树。</p>
<p>在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树</p>
<p>首先啊得了解啥是平衡二叉树</p>
<p><strong>一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值小于1。</strong></p>
<p>大于1就返回fasle呗</p>
</div>
<div id="数组中只出现一次的数" class="section level2">
<h2><span class="header-section-number">1.42</span> 数组中只出现一次的数</h2>
<p><strong>题目描述</strong>
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。</p>
<div class="sourceCode" id="cb49"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb49-1"><a href="#cb49-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb49-2"><a href="#cb49-2"></a>class Solution<span class="op">:</span></span>
<span id="cb49-3"><a href="#cb49-3"></a><span class="st">    </span><span class="co"># 返回[a,b] 其中ab是出现一次的两个数字</span></span>
<span id="cb49-4"><a href="#cb49-4"></a><span class="st">    </span>def <span class="kw">FindNumsAppearOnce</span>(self, array)<span class="op">:</span></span>
<span id="cb49-5"><a href="#cb49-5"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb49-6"><a href="#cb49-6"></a><span class="st">        </span>res=[]</span>
<span id="cb49-7"><a href="#cb49-7"></a>        <span class="cf">for</span> i <span class="cf">in</span> array<span class="op">:</span></span>
<span id="cb49-8"><a href="#cb49-8"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">array.count</span>(i)<span class="op">==</span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb49-9"><a href="#cb49-9"></a><span class="st">                </span><span class="kw">res.append</span>(i)</span>
<span id="cb49-10"><a href="#cb49-10"></a>        return res</span></code></pre></div>
</div>
<div id="和为s的连续子序列" class="section level2">
<h2><span class="header-section-number">1.43</span> 和为S的连续子序列</h2>
<p><strong>题目描述</strong></p>
<p>小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!</p>
<p><strong>思路1</strong>
在连续的正数序列中，如果一个数比和的一半要大的话，如和为100，其中一个数是51，那么，存在51且和等于100的这个序列是不存在的。因此，我们可以借助两个循环，来循环遍历所有和等于tsum的序列。</p>
<p>也就是穷举法</p>
<div class="sourceCode" id="cb50"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb50-1"><a href="#cb50-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb50-2"><a href="#cb50-2"></a>class Solution<span class="op">:</span></span>
<span id="cb50-3"><a href="#cb50-3"></a><span class="st">    </span>def <span class="kw">FindContinuousSequence</span>(self, tsum)<span class="op">:</span></span>
<span id="cb50-4"><a href="#cb50-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb50-5"><a href="#cb50-5"></a><span class="st">        </span>res =<span class="st"> </span>[]</span>
<span id="cb50-6"><a href="#cb50-6"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>, tsum<span class="op">/</span><span class="er">/</span><span class="dv">2</span><span class="op">+</span><span class="dv">1</span>)<span class="op">:</span><span class="st"> </span>遍历一半就行了</span>
<span id="cb50-7"><a href="#cb50-7"></a>            sum =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb50-8"><a href="#cb50-8"></a>            <span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(i, tsum<span class="op">/</span><span class="er">/</span><span class="dv">2</span><span class="op">+</span><span class="dv">2</span>)<span class="op">:</span></span>
<span id="cb50-9"><a href="#cb50-9"></a><span class="st">                </span>sum <span class="op">+</span><span class="er">=</span><span class="st"> </span>j</span>
<span id="cb50-10"><a href="#cb50-10"></a>                <span class="cf">if</span> sum <span class="op">==</span><span class="st"> </span>tsum<span class="op">:</span></span>
<span id="cb50-11"><a href="#cb50-11"></a><span class="st">                    </span><span class="kw">res.append</span>(<span class="kw">list</span>(<span class="kw">range</span>(i, j<span class="op">+</span><span class="dv">1</span>)))</span>
<span id="cb50-12"><a href="#cb50-12"></a>                <span class="cf">if</span> sum <span class="op">&gt;</span><span class="st"> </span>tsum<span class="op">:</span></span>
<span id="cb50-13"><a href="#cb50-13"></a><span class="st">                    </span><span class="cf">break</span></span>
<span id="cb50-14"><a href="#cb50-14"></a>        return res</span></code></pre></div>
<p><em>思路2</em></p>
<blockquote>
<p>利用一个双指针来实现一个滑动窗口，如果当前窗口内的和等于tsum，返回窗口内的所有数，并且移动窗口，窗口右侧向右移动一位或者左侧右移一位都行，如果小于tsum的话，窗口的左侧向右移动一位，如果大于tsum的话，窗口的右侧向左移动一位，循环终止条件是，窗口左侧，即（窗口左侧）序列的最小值大于tsum//2，即思路1中的不会有数大于和的一半。<a href="https://blog.csdn.net/ggdhs/article/details/90344263">csdn</a></p>
</blockquote>
<p>滑动窗口的思想真的挺常见的，要熟练使用哇</p>
<div class="sourceCode" id="cb51"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb51-1"><a href="#cb51-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb51-2"><a href="#cb51-2"></a>class Solution<span class="op">:</span></span>
<span id="cb51-3"><a href="#cb51-3"></a><span class="st">    </span>def <span class="kw">FindContinuousSequence</span>(self, tsum)<span class="op">:</span></span>
<span id="cb51-4"><a href="#cb51-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb51-5"><a href="#cb51-5"></a><span class="st">        </span><span class="cf">if</span> tsum <span class="op">==</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb51-6"><a href="#cb51-6"></a><span class="st">            </span>return []</span>
<span id="cb51-7"><a href="#cb51-7"></a>        small =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb51-8"><a href="#cb51-8"></a>        big =<span class="st"> </span><span class="dv">2</span></span>
<span id="cb51-9"><a href="#cb51-9"></a>        mid =<span class="st"> </span>tsum<span class="op">/</span><span class="er">/</span><span class="dv">2</span></span>
<span id="cb51-10"><a href="#cb51-10"></a>        sum =<span class="st"> </span>big<span class="op">+</span>small       <span class="co"># 用来不断更新当前序列的和，也可以利用求和公式。</span></span>
<span id="cb51-11"><a href="#cb51-11"></a>        ret =<span class="st"> </span>[]</span>
<span id="cb51-12"><a href="#cb51-12"></a>        <span class="cf">while</span> small <span class="op">&lt;=</span><span class="st"> </span>mid<span class="op">:</span></span>
<span id="cb51-13"><a href="#cb51-13"></a><span class="st">            </span><span class="cf">if</span> sum <span class="op">==</span><span class="st"> </span>tsum<span class="op">:</span></span>
<span id="cb51-14"><a href="#cb51-14"></a><span class="st">                </span><span class="kw">ret.append</span>(<span class="kw">list</span>(<span class="kw">range</span>(small,big<span class="op">+</span><span class="dv">1</span>)))</span>
<span id="cb51-15"><a href="#cb51-15"></a>                big <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span>       <span class="co"># 如果右侧窗口移动，先移动在加</span></span>
<span id="cb51-16"><a href="#cb51-16"></a>                sum <span class="op">+</span><span class="er">=</span><span class="st"> </span>big     <span class="co"># 不断更新，也可以利用求和公式来计算窗口内数的和</span></span>
<span id="cb51-17"><a href="#cb51-17"></a>            elif sum <span class="op">&lt;</span><span class="st"> </span>tsum<span class="op">:</span></span>
<span id="cb51-18"><a href="#cb51-18"></a><span class="st">                </span>big <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span>      </span>
<span id="cb51-19"><a href="#cb51-19"></a>                sum <span class="op">+</span><span class="er">=</span><span class="st"> </span>big</span>
<span id="cb51-20"><a href="#cb51-20"></a>            <span class="cf">else</span><span class="op">:</span><span class="st">             </span><span class="co"># 如果左侧窗口移动，先减在移动</span></span>
<span id="cb51-21"><a href="#cb51-21"></a><span class="st">                </span>sum <span class="op">-</span><span class="er">=</span><span class="st"> </span>small</span>
<span id="cb51-22"><a href="#cb51-22"></a>                small <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb51-23"><a href="#cb51-23"></a>        return ret</span></code></pre></div>
</div>
<div id="两个数之和为s" class="section level2">
<h2><span class="header-section-number">1.44</span> 两个数之和为s</h2>
<p><strong>题目描述</strong>
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。</p>
<p>easy题</p>
<div class="sourceCode" id="cb52"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb52-1"><a href="#cb52-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb52-2"><a href="#cb52-2"></a>class Solution<span class="op">:</span></span>
<span id="cb52-3"><a href="#cb52-3"></a><span class="st">    </span>def <span class="kw">FindNumbersWithSum</span>(self, array, tsum)<span class="op">:</span></span>
<span id="cb52-4"><a href="#cb52-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb52-5"><a href="#cb52-5"></a><span class="st">        </span><span class="cf">if</span> not array or not tsum<span class="op">:</span></span>
<span id="cb52-6"><a href="#cb52-6"></a><span class="st">            </span>return []</span>
<span id="cb52-7"><a href="#cb52-7"></a>        result =<span class="st"> </span>[]</span>
<span id="cb52-8"><a href="#cb52-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> array<span class="op">:</span></span>
<span id="cb52-9"><a href="#cb52-9"></a><span class="st">            </span><span class="cf">if</span> (tsum <span class="op">-</span><span class="st"> </span>i) <span class="cf">in</span> array<span class="op">:</span></span>
<span id="cb52-10"><a href="#cb52-10"></a><span class="st">                </span><span class="kw">result.append</span>([i, tsum <span class="op">-</span><span class="st"> </span>i])</span>
<span id="cb52-11"><a href="#cb52-11"></a>        <span class="cf">if</span> result<span class="op">:</span></span>
<span id="cb52-12"><a href="#cb52-12"></a><span class="st">            </span><span class="kw">result.sort</span>(<span class="dt">key=</span>lambda x<span class="op">:</span><span class="st"> </span>x[<span class="dv">0</span>] <span class="op">*</span><span class="st"> </span>x[<span class="dv">1</span>])</span>
<span id="cb52-13"><a href="#cb52-13"></a>            result =<span class="st"> </span>result[<span class="dv">0</span>]</span>
<span id="cb52-14"><a href="#cb52-14"></a>            return result</span>
<span id="cb52-15"><a href="#cb52-15"></a>        return []</span></code></pre></div>
</div>
<div id="减绳子" class="section level2">
<h2><span class="header-section-number">1.45</span> 减绳子</h2>
<p><strong>题目描述</strong></p>
<p>给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n&gt;1并且m&gt;1，m&lt;=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。</p>
<div class="sourceCode" id="cb53"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb53-1"><a href="#cb53-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb53-2"><a href="#cb53-2"></a><span class="co">#动态规划</span></span>
<span id="cb53-3"><a href="#cb53-3"></a>class Solution<span class="op">:</span></span>
<span id="cb53-4"><a href="#cb53-4"></a><span class="st">    </span>def <span class="kw">cutRope</span>(self, number)<span class="op">:</span></span>
<span id="cb53-5"><a href="#cb53-5"></a><span class="st">         </span><span class="co"># write code here</span></span>
<span id="cb53-6"><a href="#cb53-6"></a><span class="st">        </span><span class="cf">if</span> number <span class="op">&lt;</span><span class="st"> </span><span class="dv">2</span><span class="op">:</span></span>
<span id="cb53-7"><a href="#cb53-7"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb53-8"><a href="#cb53-8"></a>        <span class="cf">if</span> number <span class="op">==</span><span class="st"> </span><span class="dv">2</span><span class="op">:</span></span>
<span id="cb53-9"><a href="#cb53-9"></a><span class="st">            </span>return <span class="dv">1</span></span>
<span id="cb53-10"><a href="#cb53-10"></a>        <span class="cf">if</span> number <span class="op">==</span><span class="st"> </span><span class="dv">3</span><span class="op">:</span></span>
<span id="cb53-11"><a href="#cb53-11"></a><span class="st">            </span>return <span class="dv">2</span>       </span>
<span id="cb53-12"><a href="#cb53-12"></a>         <span class="co">#申请辅助空间</span></span>
<span id="cb53-13"><a href="#cb53-13"></a>        products =<span class="st"> </span>[<span class="dv">0</span>]<span class="op">*</span>(number<span class="op">+</span><span class="dv">1</span>)</span>
<span id="cb53-14"><a href="#cb53-14"></a>         <span class="co">#定义前几个初始变量的值</span></span>
<span id="cb53-15"><a href="#cb53-15"></a>        products[<span class="dv">0</span>] =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb53-16"><a href="#cb53-16"></a>        products[<span class="dv">1</span>] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb53-17"><a href="#cb53-17"></a>        products[<span class="dv">2</span>] =<span class="st"> </span><span class="dv">2</span></span>
<span id="cb53-18"><a href="#cb53-18"></a>        products[<span class="dv">3</span>] =<span class="st"> </span><span class="dv">3</span> <span class="co">#可以考虑先把可能出现的情况列出来</span></span>
<span id="cb53-19"><a href="#cb53-19"></a>         <span class="co">#进行动态规划,也就是从下向上的进行求解</span></span>
<span id="cb53-20"><a href="#cb53-20"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">4</span>, number<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb53-21"><a href="#cb53-21"></a><span class="st">            </span>max_ =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb53-22"><a href="#cb53-22"></a>            <span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>, i<span class="op">/</span><span class="dv">2</span><span class="op">+</span><span class="dv">1</span>)<span class="op">:</span><span class="st"> </span><span class="co">#可以用数学方法先找下范围，长方形面积问题把</span></span>
<span id="cb53-23"><a href="#cb53-23"></a><span class="st">                </span>max_ =<span class="st"> </span><span class="kw">max</span>(products[j]<span class="op">*</span>products[i<span class="op">-</span>j], max_) <span class="co">#剪出长度为j的绳子所得到饿最大的乘积，与当前最大的乘积做比较</span></span>
<span id="cb53-24"><a href="#cb53-24"></a>            products[i] =<span class="st"> </span>max_</span>
<span id="cb53-25"><a href="#cb53-25"></a>            max_ =<span class="st"> </span>products[number]</span>
<span id="cb53-26"><a href="#cb53-26"></a>        return max_</span></code></pre></div>
</div>
<div id="机器人的移动范围" class="section level2">
<h2><span class="header-section-number">1.46</span> 机器人的移动范围</h2>
<p><strong>题目描述</strong>
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？</p>
<p>需要分别计算个位和十位上面的数字
个位：取余
十位：取商</p>
<p>就正常的遍历每个格子就是正常的解法</p>
<div class="sourceCode" id="cb54"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb54-1"><a href="#cb54-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb54-2"><a href="#cb54-2"></a>class Solution<span class="op">:</span></span>
<span id="cb54-3"><a href="#cb54-3"></a><span class="st">    </span>def <span class="kw">calSum</span>(self, temp)<span class="op">:</span></span>
<span id="cb54-4"><a href="#cb54-4"></a><span class="st">        </span>sum =<span class="st"> </span><span class="dv">0</span> <span class="co">#两数的和</span></span>
<span id="cb54-5"><a href="#cb54-5"></a>        <span class="cf">while</span>(temp <span class="op">!=</span><span class="st"> </span><span class="dv">0</span>)<span class="op">:</span></span>
<span id="cb54-6"><a href="#cb54-6"></a><span class="st">            </span>sum <span class="op">+</span><span class="er">=</span><span class="st"> </span>temp % <span class="dv">10</span> <span class="co"># 取到个位数</span></span>
<span id="cb54-7"><a href="#cb54-7"></a>            temp =<span class="st"> </span>temp <span class="op">/</span><span class="st"> </span><span class="dv">10</span>  <span class="co">#取到十位数</span></span>
<span id="cb54-8"><a href="#cb54-8"></a>        return sum</span>
<span id="cb54-9"><a href="#cb54-9"></a>      </span>
<span id="cb54-10"><a href="#cb54-10"></a>    def <span class="kw">movingCount</span>(self, threshold, rows, cols)<span class="op">:</span></span>
<span id="cb54-11"><a href="#cb54-11"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb54-12"><a href="#cb54-12"></a><span class="st">        </span>num =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb54-13"><a href="#cb54-13"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(rows)<span class="op">:</span></span>
<span id="cb54-14"><a href="#cb54-14"></a><span class="st">            </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(cols)<span class="op">:</span></span>
<span id="cb54-15"><a href="#cb54-15"></a><span class="st">                </span><span class="cf">if</span>(<span class="kw">self.calSum</span>(i) <span class="op">+</span><span class="st"> </span><span class="kw">self.calSum</span>(j) <span class="op">&lt;=</span><span class="st"> </span>threshold)<span class="op">:</span></span>
<span id="cb54-16"><a href="#cb54-16"></a><span class="st">                    </span>num =<span class="st"> </span>num <span class="op">+</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb54-17"><a href="#cb54-17"></a>                <span class="kw">elif</span>(rows<span class="op">==</span><span class="dv">1</span> or cols<span class="op">==</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb54-18"><a href="#cb54-18"></a><span class="st">                    </span>return num</span>
<span id="cb54-19"><a href="#cb54-19"></a>        return num</span></code></pre></div>
</div>
<div id="矩阵中的路径" class="section level2">
<h2><span class="header-section-number">1.47</span> 矩阵中的路径</h2>
<p><strong>题目描述</strong>
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 <span class="math inline">\(\left[\begin{array}{llll}a &amp; b &amp; c &amp; e \\ s &amp; f &amp; c &amp; s \\ a &amp; d &amp; e &amp; e\end{array}\right]\)</span>
矩阵中包含一条字符串“bcced”的路径，但是矩阵中不包含“abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。</p>
<p>不太会</p>
<div class="sourceCode" id="cb55"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb55-1"><a href="#cb55-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb55-2"><a href="#cb55-2"></a>class Solution<span class="op">:</span></span>
<span id="cb55-3"><a href="#cb55-3"></a><span class="st">    </span>def <span class="kw">hasPath</span>(self, matrix, rows, cols, path)<span class="op">:</span></span>
<span id="cb55-4"><a href="#cb55-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb55-5"><a href="#cb55-5"></a><span class="st">        </span><span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(rows)<span class="op">:</span></span>
<span id="cb55-6"><a href="#cb55-6"></a><span class="st">            </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span> (cols)<span class="op">:</span></span>
<span id="cb55-7"><a href="#cb55-7"></a><span class="st">                </span><span class="cf">if</span> matrix[i<span class="op">*</span>cols<span class="op">+</span>j]<span class="op">==</span>path[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb55-8"><a href="#cb55-8"></a><span class="st">                    </span><span class="cf">if</span> <span class="kw">self.findpath</span>(i,j,path[<span class="dv">1</span><span class="op">:</span>],<span class="kw">list</span>(matrix),rows,cols)<span class="op">:</span></span>
<span id="cb55-9"><a href="#cb55-9"></a><span class="st">                        </span>return True</span>
<span id="cb55-10"><a href="#cb55-10"></a>        return False</span>
<span id="cb55-11"><a href="#cb55-11"></a>    def <span class="kw">findpath</span>(self,i,j,path,matrix,rows,cols)<span class="op">:</span></span>
<span id="cb55-12"><a href="#cb55-12"></a><span class="st">        </span><span class="cf">if</span> i<span class="op">&lt;</span><span class="dv">0</span> or j<span class="op">&lt;</span><span class="dv">0</span> or i<span class="op">&gt;</span>rows or j<span class="op">&gt;</span>cols<span class="op">:</span></span>
<span id="cb55-13"><a href="#cb55-13"></a><span class="st">            </span>return False</span>
<span id="cb55-14"><a href="#cb55-14"></a>        <span class="cf">if</span> not path<span class="op">:</span></span>
<span id="cb55-15"><a href="#cb55-15"></a><span class="st">            </span>return True</span>
<span id="cb55-16"><a href="#cb55-16"></a>        matrix[i<span class="op">*</span>cols<span class="op">+</span>j]=<span class="st">&#39;0&#39;</span></span>
<span id="cb55-17"><a href="#cb55-17"></a>        <span class="cf">if</span> i<span class="op">+</span><span class="dv">1</span><span class="op">&lt;</span>rows and matrix[(i<span class="op">+</span><span class="dv">1</span>)<span class="op">*</span>cols<span class="op">+</span>j]<span class="op">==</span>path[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb55-18"><a href="#cb55-18"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">self.findpath</span>(i<span class="op">+</span><span class="dv">1</span>, j, path[<span class="dv">1</span><span class="op">:</span>], matrix, rows, cols)<span class="op">:</span></span>
<span id="cb55-19"><a href="#cb55-19"></a><span class="st">                </span>return True</span>
<span id="cb55-20"><a href="#cb55-20"></a>        <span class="cf">if</span> j<span class="op">+</span><span class="dv">1</span><span class="op">&lt;</span>cols and matrix[i<span class="op">*</span>cols<span class="op">+</span>j<span class="op">+</span><span class="dv">1</span>]<span class="op">==</span>path[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb55-21"><a href="#cb55-21"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">self.findpath</span>(i, j<span class="op">+</span><span class="dv">1</span>, path[<span class="dv">1</span><span class="op">:</span>], matrix, rows, cols)<span class="op">:</span></span>
<span id="cb55-22"><a href="#cb55-22"></a><span class="st">                </span>return True</span>
<span id="cb55-23"><a href="#cb55-23"></a>        <span class="cf">if</span> i<span class="dv">-1</span><span class="op">&gt;=</span><span class="dv">0</span> and matrix[(i<span class="dv">-1</span>)<span class="op">*</span>cols<span class="op">+</span>j]<span class="op">==</span>path[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb55-24"><a href="#cb55-24"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">self.findpath</span>(i<span class="dv">-1</span>, j, path[<span class="dv">1</span><span class="op">:</span>], matrix, rows, cols)<span class="op">:</span></span>
<span id="cb55-25"><a href="#cb55-25"></a><span class="st">                </span>return True</span>
<span id="cb55-26"><a href="#cb55-26"></a>        <span class="cf">if</span> j<span class="dv">-1</span><span class="op">&gt;=</span><span class="dv">0</span> and matrix[i<span class="op">*</span>cols<span class="op">+</span>j<span class="dv">-1</span>]<span class="op">==</span>path[<span class="dv">0</span>]<span class="op">:</span></span>
<span id="cb55-27"><a href="#cb55-27"></a><span class="st">            </span><span class="cf">if</span> <span class="kw">self.findpath</span>(i, j<span class="dv">-1</span>, path[<span class="dv">1</span><span class="op">:</span>], matrix, rows, cols)<span class="op">:</span></span>
<span id="cb55-28"><a href="#cb55-28"></a><span class="st">                </span>return True</span>
<span id="cb55-29"><a href="#cb55-29"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb55-30"><a href="#cb55-30"></a><span class="st">            </span>return False</span></code></pre></div>
</div>
<div id="滑动窗口的最大值" class="section level2">
<h2><span class="header-section-number">1.48</span> 滑动窗口的最大值</h2>
<div class="sourceCode" id="cb56"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb56-1"><a href="#cb56-1"></a>题目描述</span>
<span id="cb56-2"><a href="#cb56-2"></a>给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>,<span class="dv">2</span>,<span class="dv">6</span>,<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{<span class="dv">4</span>,<span class="dv">4</span>,<span class="dv">6</span>,<span class="dv">6</span>,<span class="dv">6</span>,<span class="dv">5</span>}； 针对数组{<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>,<span class="dv">2</span>,<span class="dv">6</span>,<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>}的滑动窗口有以下6个： {[<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>],<span class="dv">2</span>,<span class="dv">6</span>,<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>}， {<span class="dv">2</span>,[<span class="dv">3</span>,<span class="dv">4</span>,<span class="dv">2</span>],<span class="dv">6</span>,<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>}， {<span class="dv">2</span>,<span class="dv">3</span>,[<span class="dv">4</span>,<span class="dv">2</span>,<span class="dv">6</span>],<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>}， {<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>,[<span class="dv">2</span>,<span class="dv">6</span>,<span class="dv">2</span>],<span class="dv">5</span>,<span class="dv">1</span>}， {<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>,<span class="dv">2</span>,[<span class="dv">6</span>,<span class="dv">2</span>,<span class="dv">5</span>],<span class="dv">1</span>}， {<span class="dv">2</span>,<span class="dv">3</span>,<span class="dv">4</span>,<span class="dv">2</span>,<span class="dv">6</span>,[<span class="dv">2</span>,<span class="dv">5</span>,<span class="dv">1</span>]}。</span>
<span id="cb56-3"><a href="#cb56-3"></a>窗口大于数组长度的时候，返回空</span></code></pre></div>
<p>想起了卷积核滑窗有木有</p>
<div class="sourceCode" id="cb57"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb57-1"><a href="#cb57-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb57-2"><a href="#cb57-2"></a>class Solution<span class="op">:</span></span>
<span id="cb57-3"><a href="#cb57-3"></a><span class="st">    </span>def <span class="kw">maxInWindows</span>(self, num, size)<span class="op">:</span></span>
<span id="cb57-4"><a href="#cb57-4"></a><span class="st">        </span><span class="cf">if</span> size<span class="op">==</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb57-5"><a href="#cb57-5"></a><span class="st">            </span>return []</span>
<span id="cb57-6"><a href="#cb57-6"></a>        <span class="cf">if</span> size<span class="op">&gt;</span><span class="kw">len</span>(num)<span class="op">:</span></span>
<span id="cb57-7"><a href="#cb57-7"></a><span class="st">            </span>return []</span>
<span id="cb57-8"><a href="#cb57-8"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb57-9"><a href="#cb57-9"></a><span class="st">            </span>result=[]</span>
<span id="cb57-10"><a href="#cb57-10"></a>            <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(num)<span class="op">-</span>size<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb57-11"><a href="#cb57-11"></a><span class="st">                </span><span class="kw">result.append</span>(<span class="kw">max</span>(num[i<span class="op">:</span>i<span class="op">+</span>size]))</span>
<span id="cb57-12"><a href="#cb57-12"></a>            return result</span></code></pre></div>
</div>
<div id="孩子们的游戏" class="section level2">
<h2><span class="header-section-number">1.49</span> 孩子们的游戏</h2>
<p><strong>题目描述</strong>
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)</p>
<p>思路1：建一个标志数组来判断某人是否还在圈内，设置变量k，k &gt; n-1时，赋k=0，表示n-1号报完数就该0号报数，最后检测标志数组为true的人。</p>
<p><strong>思路2：</strong>用数学归纳法推导出递推公式，设有n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。令f[i]表示i个人时最后胜利者的编号，则有递推公式：
f[1]=0;
f[i]=(f[i-1]+m)%i; (i&gt;1)
通过递推公式即可求得f[n]。</p>
<div class="sourceCode" id="cb58"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb58-1"><a href="#cb58-1"></a>def <span class="kw">LastRemaining_Solution</span>(self, n, m)<span class="op">:</span></span>
<span id="cb58-2"><a href="#cb58-2"></a><span class="st">    </span><span class="co"># write code here</span></span>
<span id="cb58-3"><a href="#cb58-3"></a><span class="st">    </span><span class="cf">if</span> n <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb58-4"><a href="#cb58-4"></a><span class="st">        </span>return <span class="dv">-1</span></span>
<span id="cb58-5"><a href="#cb58-5"></a>    s =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb58-6"><a href="#cb58-6"></a>    <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">2</span>, n<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb58-7"><a href="#cb58-7"></a><span class="st">        </span>s =<span class="st"> </span>(s<span class="op">+</span>m) % i</span>
<span id="cb58-8"><a href="#cb58-8"></a>    return s</span></code></pre></div>
</div>
<div id="扑克牌的顺子" class="section level2">
<h2><span class="header-section-number">1.50</span> 扑克牌的顺子</h2>
<p><strong>题目描述</strong></p>
<p>LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。</p>
<p><strong>思路：</strong>看是否连续就是看中间缺少的部分能否用大小王，即0来填充，因此只需要比较0的个数和中间缺少的个数就行了，如果中间缺少的比0的数目多，即大小王的个数不足以将缺少的填充，那么就不连续了</p>
<p>首先你得读懂题</p>
<ul>
<li>除0外，最大值与最小值之差小于等于4</li>
<li>除0外，不能在包含其它重复的牌</li>
</ul>
<div class="sourceCode" id="cb59"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb59-1"><a href="#cb59-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb59-2"><a href="#cb59-2"></a>class Solution<span class="op">:</span></span>
<span id="cb59-3"><a href="#cb59-3"></a><span class="st">    </span>def <span class="kw">IsContinuous</span>(self, numbers)<span class="op">:</span></span>
<span id="cb59-4"><a href="#cb59-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb59-5"><a href="#cb59-5"></a><span class="st">        </span><span class="cf">if</span> not numbers<span class="op">:</span></span>
<span id="cb59-6"><a href="#cb59-6"></a><span class="st">            </span>return False</span>
<span id="cb59-7"><a href="#cb59-7"></a>        res =<span class="st"> </span>[]</span>
<span id="cb59-8"><a href="#cb59-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> numbers<span class="op">:</span></span>
<span id="cb59-9"><a href="#cb59-9"></a><span class="st">            </span><span class="cf">if</span> i <span class="op">&gt;</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb59-10"><a href="#cb59-10"></a><span class="st">                </span><span class="kw">res.append</span>(i)</span>
<span id="cb59-11"><a href="#cb59-11"></a>        <span class="cf">if</span> <span class="kw">max</span>(res) <span class="op">-</span><span class="st"> </span><span class="kw">min</span>(res) <span class="op">&lt;=</span><span class="st"> </span><span class="dv">4</span> and <span class="kw">len</span>(res) <span class="op">==</span><span class="st"> </span><span class="kw">len</span>(<span class="kw">set</span>(res))<span class="op">:</span></span>
<span id="cb59-12"><a href="#cb59-12"></a><span class="st">            </span>return True</span>
<span id="cb59-13"><a href="#cb59-13"></a>        return False</span></code></pre></div>
</div>
<div id="将字符串转化为整数" class="section level2">
<h2><span class="header-section-number">1.51</span> 将字符串转化为整数</h2>
<p><strong>题目描述</strong>
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0</p>
<div class="sourceCode" id="cb60"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb60-1"><a href="#cb60-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb60-2"><a href="#cb60-2"></a>class Solution<span class="op">:</span></span>
<span id="cb60-3"><a href="#cb60-3"></a><span class="st">    </span>def <span class="kw">StrToInt</span>(self, s)<span class="op">:</span></span>
<span id="cb60-4"><a href="#cb60-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb60-5"><a href="#cb60-5"></a><span class="st">        </span><span class="cf">if</span> not s or <span class="kw">len</span>(s) <span class="op">&lt;</span><span class="st"> </span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb60-6"><a href="#cb60-6"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb60-7"><a href="#cb60-7"></a>        numdict =<span class="st"> </span>{<span class="st">&#39;0&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">0</span>, <span class="st">&#39;1&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">1</span>, <span class="st">&#39;2&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">2</span>, <span class="st">&#39;3&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">3</span>, <span class="st">&#39;4&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">4</span>, <span class="st">&#39;5&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">5</span>, <span class="st">&#39;6&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">6</span>, <span class="st">&#39;7&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">7</span>, <span class="st">&#39;8&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">8</span>, <span class="st">&#39;9&#39;</span><span class="op">:</span><span class="st"> </span><span class="dv">9</span>}</span>
<span id="cb60-8"><a href="#cb60-8"></a>        result =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb60-9"><a href="#cb60-9"></a>        nums =<span class="st"> </span>[]</span>
<span id="cb60-10"><a href="#cb60-10"></a>        <span class="cf">for</span> char <span class="cf">in</span> s<span class="op">:</span></span>
<span id="cb60-11"><a href="#cb60-11"></a><span class="st">            </span><span class="cf">if</span> char <span class="op">==</span><span class="st"> &#39;+&#39;</span> or char <span class="op">==</span><span class="st"> &#39;-&#39;</span><span class="op">:</span></span>
<span id="cb60-12"><a href="#cb60-12"></a><span class="st">                </span>continue</span>
<span id="cb60-13"><a href="#cb60-13"></a>            elif char <span class="cf">in</span> numdict<span class="op">:</span></span>
<span id="cb60-14"><a href="#cb60-14"></a><span class="st">                </span><span class="kw">nums.append</span>(numdict[char])</span>
<span id="cb60-15"><a href="#cb60-15"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb60-16"><a href="#cb60-16"></a><span class="st">                </span>return <span class="dv">0</span></span>
<span id="cb60-17"><a href="#cb60-17"></a>        <span class="co"># 由list得到数值，这个写法要会</span></span>
<span id="cb60-18"><a href="#cb60-18"></a>        <span class="cf">for</span> i <span class="cf">in</span> nums<span class="op">:</span></span>
<span id="cb60-19"><a href="#cb60-19"></a><span class="st">            </span>result =<span class="st"> </span>result<span class="op">*</span><span class="dv">10</span> <span class="op">+</span><span class="st"> </span>i</span>
<span id="cb60-20"><a href="#cb60-20"></a>        return <span class="dv">-1</span><span class="op">*</span>result <span class="cf">if</span> s[<span class="dv">0</span>] <span class="op">==</span><span class="st"> &#39;-&#39;</span> <span class="cf">else</span> result</span></code></pre></div>
</div>
<div id="数组中第一个重复数字" class="section level2">
<h2><span class="header-section-number">1.52</span> 数组中第一个重复数字</h2>
<p>题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。</p>
<div class="sourceCode" id="cb61"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb61-1"><a href="#cb61-1"></a>class Solution<span class="op">:</span></span>
<span id="cb61-2"><a href="#cb61-2"></a><span class="st">    </span><span class="co"># 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]</span></span>
<span id="cb61-3"><a href="#cb61-3"></a><span class="st">    </span><span class="co"># 函数返回True/False</span></span>
<span id="cb61-4"><a href="#cb61-4"></a><span class="st">    </span>def <span class="kw">duplicate</span>(self, numbers, duplication)<span class="op">:</span></span>
<span id="cb61-5"><a href="#cb61-5"></a><span class="st">        </span><span class="cf">for</span> i <span class="cf">in</span> numbers<span class="op">:</span></span>
<span id="cb61-6"><a href="#cb61-6"></a><span class="st">            </span><span class="cf">if</span> i not <span class="cf">in</span> duplication<span class="op">:</span></span>
<span id="cb61-7"><a href="#cb61-7"></a><span class="st">                </span><span class="kw">duplication.append</span>(i)</span>
<span id="cb61-8"><a href="#cb61-8"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb61-9"><a href="#cb61-9"></a><span class="st">                </span>duplication[<span class="dv">0</span>]=i</span>
<span id="cb61-10"><a href="#cb61-10"></a>                return True</span>
<span id="cb61-11"><a href="#cb61-11"></a>        return False</span></code></pre></div>
</div>
<div id="构建乘积数组" class="section level2">
<h2><span class="header-section-number">1.53</span> 构建乘积数组</h2>
<p><strong>题目描述</strong></p>
<p>给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]<em>A[1]</em>…<em>A[i-1]</em>A[i+1]<em>…</em>A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。</p>
<div class="sourceCode" id="cb62"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb62-1"><a href="#cb62-1"></a></span>
<span id="cb62-2"><a href="#cb62-2"></a>class Solution<span class="op">:</span></span>
<span id="cb62-3"><a href="#cb62-3"></a><span class="st">    </span>def <span class="kw">multiply</span>(self, A)<span class="op">:</span></span>
<span id="cb62-4"><a href="#cb62-4"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb62-5"><a href="#cb62-5"></a><span class="st">        </span>length =<span class="st"> </span><span class="kw">len</span>(A)</span>
<span id="cb62-6"><a href="#cb62-6"></a>        B =<span class="st"> </span>[]</span>
<span id="cb62-7"><a href="#cb62-7"></a>        <span class="cf">if</span>(length <span class="op">==</span><span class="st"> </span><span class="dv">0</span>)<span class="op">:</span></span>
<span id="cb62-8"><a href="#cb62-8"></a><span class="st">            </span>return B</span>
<span id="cb62-9"><a href="#cb62-9"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(length)<span class="op">:</span></span>
<span id="cb62-10"><a href="#cb62-10"></a><span class="st">            </span>temp =<span class="st"> </span>A[i]</span>
<span id="cb62-11"><a href="#cb62-11"></a>            A[i] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb62-12"><a href="#cb62-12"></a>            Bi =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb62-13"><a href="#cb62-13"></a>            <span class="cf">for</span> j <span class="cf">in</span> A<span class="op">:</span></span>
<span id="cb62-14"><a href="#cb62-14"></a><span class="st">                </span>Bi <span class="op">*</span><span class="er">=</span><span class="st"> </span>j</span>
<span id="cb62-15"><a href="#cb62-15"></a>            <span class="kw">B.append</span>(Bi)</span>
<span id="cb62-16"><a href="#cb62-16"></a>            A[i] =<span class="st"> </span>temp</span>
<span id="cb62-17"><a href="#cb62-17"></a>        return B</span></code></pre></div>
</div>
<div id="字符串中第一个不重复得字符串" class="section level2">
<h2><span class="header-section-number">1.54</span> 字符串中第一个不重复得字符串</h2>
<p><strong>题目描述</strong></p>
<p>请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是“g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是“l”。</p>
<p>找个辅助栈</p>
<div class="sourceCode" id="cb63"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb63-1"><a href="#cb63-1"></a>class Solution<span class="op">:</span></span>
<span id="cb63-2"><a href="#cb63-2"></a><span class="st">    </span><span class="co"># 返回对应char</span></span>
<span id="cb63-3"><a href="#cb63-3"></a><span class="st">    </span>def <span class="kw">__init__</span>(self)<span class="op">:</span></span>
<span id="cb63-4"><a href="#cb63-4"></a><span class="st">        </span>self.s=<span class="st">&#39;&#39;</span></span>
<span id="cb63-5"><a href="#cb63-5"></a>    def <span class="kw">FirstAppearingOnce</span>(self)<span class="op">:</span></span>
<span id="cb63-6"><a href="#cb63-6"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb63-7"><a href="#cb63-7"></a><span class="st">        </span>res=[]</span>
<span id="cb63-8"><a href="#cb63-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> self.s<span class="op">:</span></span>
<span id="cb63-9"><a href="#cb63-9"></a><span class="st">            </span><span class="cf">if</span> i <span class="cf">in</span> res<span class="op">:</span></span>
<span id="cb63-10"><a href="#cb63-10"></a><span class="st">                </span><span class="kw">res.remove</span>(i)</span>
<span id="cb63-11"><a href="#cb63-11"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb63-12"><a href="#cb63-12"></a><span class="st">                </span><span class="kw">res.append</span>(i)</span>
<span id="cb63-13"><a href="#cb63-13"></a>        return res[<span class="dv">0</span>] <span class="cf">if</span> res <span class="cf">else</span> <span class="st">&quot;#&quot;</span></span>
<span id="cb63-14"><a href="#cb63-14"></a>    def <span class="kw">Insert</span>(self, char)<span class="op">:</span></span>
<span id="cb63-15"><a href="#cb63-15"></a><span class="st">        </span><span class="co"># write code here</span></span>
<span id="cb63-16"><a href="#cb63-16"></a><span class="st">        </span>self.s<span class="op">+</span><span class="er">=</span>char</span></code></pre></div>
</div>
<div id="数流中得中位数" class="section level2">
<h2><span class="header-section-number">1.55</span> 数流中得中位数</h2>
<p><strong>题目描述</strong></p>
<p>如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。</p>
<div class="sourceCode" id="cb64"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb64-1"><a href="#cb64-1"></a><span class="co"># -*- coding:utf-8 -*-</span></span>
<span id="cb64-2"><a href="#cb64-2"></a>class Solution<span class="op">:</span></span>
<span id="cb64-3"><a href="#cb64-3"></a><span class="st">    </span>def <span class="kw">__init__</span>(self)<span class="op">:</span></span>
<span id="cb64-4"><a href="#cb64-4"></a><span class="st">        </span>self.data =<span class="st"> </span>[]</span>
<span id="cb64-5"><a href="#cb64-5"></a>    def <span class="kw">Insert</span>(self, num)<span class="op">:</span></span>
<span id="cb64-6"><a href="#cb64-6"></a><span class="st">        </span><span class="kw">self.data.append</span>(num)</span>
<span id="cb64-7"><a href="#cb64-7"></a>        <span class="kw">self.data.sort</span>()</span>
<span id="cb64-8"><a href="#cb64-8"></a>    def <span class="kw">GetMedian</span>(self,data)<span class="op">:</span></span>
<span id="cb64-9"><a href="#cb64-9"></a><span class="st">        </span>length =<span class="st"> </span><span class="kw">len</span>(self.data)</span>
<span id="cb64-10"><a href="#cb64-10"></a>        <span class="cf">if</span> length%<span class="dv">2</span><span class="op">==</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb64-11"><a href="#cb64-11"></a><span class="st">            </span><span class="kw">return</span> (self.data[length<span class="op">/</span><span class="er">/</span><span class="dv">2</span>]<span class="op">+</span>self.data[length<span class="op">/</span><span class="er">/</span><span class="dv">2-1</span>])<span class="op">/</span><span class="fl">2.0</span></span>
<span id="cb64-12"><a href="#cb64-12"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb64-13"><a href="#cb64-13"></a><span class="st">            </span>return self.data[length<span class="op">/</span><span class="er">/</span><span class="dv">2</span>]</span></code></pre></div>
<p>有一部分二叉树的题，我就先不放了，因为我确实没摸索好二叉树的题咋写才能通过</p>
<p>下面就是复习两边，掌握 核心的idea即可</p>
</div>
<div id="求n个骰子各点数和出现的概率" class="section level2">
<h2><span class="header-section-number">1.56</span> 求n个骰子各点数和出现的概率</h2>
<p>题目描述：</p>
<p>把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值的出现概率。</p>
<p>思路：定义两个数组。数组的长度为6*n,即可能出现的最大和。数组每个元素的值代表出现的次数，比如probability[5]表示点数和为5出现的次数。在一轮循环中，一个数组记录之前一次所有出现的情况，一个数组记录这一次的所有出现的情况。例如这一次出现和为n的次数，应该等于另一个数组里记录的n-1,n-2, n-3, n-4, n-5, n-6的和。</p>
<p>思路2：</p>
<p>分析：动态规划就是分阶段考虑问题，给出变量，找出相邻阶段间的关系。具体定义给忘了。</p>
<p>1.现在变量有：骰子个数，点数和。当有k个骰子，点数和为n时，出现次数记为f(k,n)。那与k-1个骰子阶段之间的关系是怎样的？</p>
<p>2.当我有k-1个骰子时，再增加一个骰子，这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有：</p>
<p>(k-1,n-1)：第k个骰子投了点数1</p>
<p>(k-1,n-2)：第k个骰子投了点数2</p>
<p>(k-1,n-3)：第k个骰子投了点数3</p>
<p>….</p>
<p>(k-1,n-6)：第k个骰子投了点数6</p>
<p>在k-1个骰子的基础上，再增加一个骰子出现点数和为n的结果只有这6种情况！</p>
<p>所以：f(k,n)=f(k-1,n-1)+f(k-1,n-2)+f(k-1,n-3)+f(k-1,n-4)+f(k-1,n-5)+f(k-1,n-6)</p>
<p>3.有1个骰子，f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。</p>
<div class="sourceCode" id="cb65"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb65-1"><a href="#cb65-1"></a>class Solution<span class="op">:</span></span>
<span id="cb65-2"><a href="#cb65-2"></a><span class="st">    </span>def <span class="kw">twoSum</span>(self, n)<span class="op">:</span></span>
<span id="cb65-3"><a href="#cb65-3"></a><span class="st">        </span><span class="co">#构建dp数组</span></span>
<span id="cb65-4"><a href="#cb65-4"></a><span class="st">        </span>dp =<span class="st"> </span>[[<span class="dv">0</span>] <span class="op">*</span><span class="st"> </span>(<span class="dv">6</span><span class="op">*</span>n<span class="op">+</span><span class="dv">1</span>) <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(n<span class="op">+</span><span class="dv">1</span>)]</span>
<span id="cb65-5"><a href="#cb65-5"></a>        <span class="co"># dp = [ [0 for _ in range(6*n+1)] for _ in range(n+1)]</span></span>
<span id="cb65-6"><a href="#cb65-6"></a>        <span class="co">#初始化操作</span></span>
<span id="cb65-7"><a href="#cb65-7"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>,<span class="dv">7</span>)<span class="op">:</span></span>
<span id="cb65-8"><a href="#cb65-8"></a><span class="st">            </span>dp[<span class="dv">1</span>][i] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb65-9"><a href="#cb65-9"></a>        <span class="co">#建立动态规划</span></span>
<span id="cb65-10"><a href="#cb65-10"></a>        <span class="co">#建立两层for循环，第一层表示骰子的数量，第二层表示和的数量</span></span>
<span id="cb65-11"><a href="#cb65-11"></a>        <span class="co">#第三层表示每个骰子可以取的点数</span></span>
<span id="cb65-12"><a href="#cb65-12"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">2</span>, n <span class="op">+</span><span class="st"> </span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb65-13"><a href="#cb65-13"></a></span>
<span id="cb65-14"><a href="#cb65-14"></a><span class="st">            </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(i, <span class="dv">6</span><span class="op">*</span>i <span class="op">+</span><span class="st"> </span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb65-15"><a href="#cb65-15"></a></span>
<span id="cb65-16"><a href="#cb65-16"></a><span class="st">                </span><span class="cf">for</span> cur <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>, <span class="dv">7</span>)<span class="op">:</span></span>
<span id="cb65-17"><a href="#cb65-17"></a></span>
<span id="cb65-18"><a href="#cb65-18"></a><span class="st">                    </span><span class="cf">if</span> j <span class="op">&gt;</span><span class="st"> </span>cur<span class="op">:</span></span>
<span id="cb65-19"><a href="#cb65-19"></a><span class="st">                        </span>dp[i][j] <span class="op">+</span><span class="er">=</span><span class="st"> </span>dp[i <span class="op">-</span><span class="st"> </span><span class="dv">1</span>][j <span class="op">-</span><span class="st"> </span>cur]</span>
<span id="cb65-20"><a href="#cb65-20"></a>        <span class="co">#然后计算概率</span></span>
<span id="cb65-21"><a href="#cb65-21"></a>        <span class="co"># sum_num = math.pow(6,n)</span></span>
<span id="cb65-22"><a href="#cb65-22"></a>        result =<span class="st"> </span>[]</span>
<span id="cb65-23"><a href="#cb65-23"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(n, <span class="dv">6</span> <span class="op">*</span><span class="st"> </span>n <span class="op">+</span><span class="st"> </span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb65-24"><a href="#cb65-24"></a><span class="st">            </span><span class="kw">result.append</span>(dp[n][i]<span class="op">*</span><span class="fl">1.0</span><span class="op">/</span><span class="dv">6</span><span class="op">**</span>n)</span>
<span id="cb65-25"><a href="#cb65-25"></a>        return result</span></code></pre></div>
</div>
</div>
            </section>

          </div>
        </div>
      </div>


    </div>
  </div>
<script src="libs/gitbook-2.6.7/js/app.min.js"></script>
<script src="libs/gitbook-2.6.7/js/lunr.js"></script>
<script src="libs/gitbook-2.6.7/js/clipboard.min.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-search.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-sharing.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-fontsettings.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-bookdown.js"></script>
<script src="libs/gitbook-2.6.7/js/jquery.highlight.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-clipboard.js"></script>
<script>
gitbook.require(["gitbook"], function(gitbook) {
gitbook.start({
"sharing": {
"github": false,
"facebook": true,
"twitter": true,
"linkedin": false,
"weibo": false,
"instapaper": false,
"vk": false,
"all": ["facebook", "twitter", "linkedin", "weibo", "instapaper"]
},
"fontsettings": {
"theme": "white",
"family": "sans",
"size": 2
},
"edit": {
"link": null,
"text": null
},
"history": {
"link": null,
"text": null
},
"view": {
"link": null,
"text": null
},
"download": null,
"toc": {
"collapse": "subsection"
},
"search": false
});
});
</script>

<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
  (function () {
    var script = document.createElement("script");
    script.type = "text/javascript";
    var src = "true";
    if (src === "" || src === "true") src = "https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-MML-AM_CHTML";
    if (location.protocol !== "file:")
      if (/^https?:/.test(src))
        src = src.replace(/^https?:/, '');
    script.src = src;
    document.getElementsByTagName("head")[0].appendChild(script);
  })();
</script>
</body>

</html>
